I found using MVVM with MenuItems to be very challenging. The rest of my application uses DataTemplates to pair the View with the ViewModel, but that just doesn't seem to work with Menus because of exactly the reasons you've described. Here's how I eventually solved it. My View looks like this:
<DockPanel>
<Menu DockPanel.Dock="Top" ItemsSource="{Binding Path=(local:MainViewModel.MainMenu)}">
<Menu.ItemContainerStyle>
<Style>
<Setter Property="MenuItem.Header" Value="{Binding Path=(contracts:IMenuItem.Header)}"/>
<Setter Property="MenuItem.ItemsSource" Value="{Binding Path=(contracts:IMenuItem.Items)}"/>
<Setter Property="MenuItem.Icon" Value="{Binding Path=(contracts:IMenuItem.Icon)}"/>
<Setter Property="MenuItem.IsCheckable" Value="{Binding Path=(contracts:IMenuItem.IsCheckable)}"/>
<Setter Property="MenuItem.IsChecked" Value="{Binding Path=(contracts:IMenuItem.IsChecked)}"/>
<Setter Property="MenuItem.Command" Value="{Binding}"/>
<Setter Property="MenuItem.Visibility" Value="{Binding Path=(contracts:IMenuItem.Visible),
Converter={StaticResource BooleanToVisibilityConverter}}"/>
<Setter Property="MenuItem.ToolTip" Value="{Binding Path=(contracts:IMenuItem.ToolTip)}"/>
<Style.Triggers>
<DataTrigger Binding="{Binding Path=(contracts:IMenuItem.IsSeparator)}" Value="true">
<Setter Property="MenuItem.Template">
<Setter.Value>
<ControlTemplate TargetType="{x:Type MenuItem}">
<Separator Style="{DynamicResource {x:Static MenuItem.SeparatorStyleKey}}"/>
</ControlTemplate>
</Setter.Value>
</Setter>
</DataTrigger>
</Style.Triggers>
</Style>
</Menu.ItemContainerStyle>
</Menu>
</DockPanel>
If you notice, I defined an interface called IMenuItem, which is the ViewModel for a MenuItem. Here's the code for that:
public interface IMenuItem : ICommand
{
string Header { get; }
IEnumerable<IMenuItem> Items { get; }
object Icon { get; }
bool IsCheckable { get; }
bool IsChecked { get; set; }
bool Visible { get; }
bool IsSeparator { get; }
string ToolTip { get; }
}
Notice that the IMenuItem defines IEnumerable Items, which is how you get sub-menus. Also, the IsSeparator is a way to define separators in the menu (another tough little trick). You can see in the xaml how it uses a DataTrigger to change the style to the existing separator style if IsSeparator is true. Here's how MainViewModel defines the MainMenu property (that the view binds to):
public IEnumerable<IMenuItem> MainMenu { get; set; }
This seems to work well. I assume you could use an ObservableCollection for the MainMenu. I'm actually using MEF to compose the menu out of parts, but after that the items themselves are static (even though the properties of each menu item are not). I also use an AbstractMenuItem class that implements IMenuItem and is a helper class to instantiate menu items in the various parts.
UPDATE:
Regarding your color problem, does this thread help?