Я обнаружил, что использовать MVVM с MenuItems очень сложно. Остальная часть моего приложения использует DataTemplates для сопряжения View с ViewModel, но это, похоже, не работает с Menus именно по причинам, которые вы описали. Вот как я в итоге решил это. Мой вид выглядит так:

<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>

Если вы заметили, я определил интерфейс под названием IMenuItem, который является ViewModel для MenuItem. Вот код для этого:

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; }
}

Обратите внимание, что IMenuItem определяет элементы IEnumerable, поэтому вы получаете подменю. Кроме того, IsSeparator - это способ определения разделителей в меню (еще один сложный маленький трюк). Вы можете увидеть в xaml, как он использует DataTrigger для изменения стиля на существующий стиль разделителя, если IsSeparator истинно. Вот как MainViewModel определяет свойство MainMenu (к которому привязывается представление):

public IEnumerable<IMenuItem> MainMenu { get; set; }

Кажется, это хорошо работает. Я предполагаю, что вы могли бы использовать ObservableCollection для MainMenu. На самом деле я использую MEF для составления меню из частей, но после этого сами элементы статичны (хотя свойства каждого элемента меню не являются). Я также использую класс AbstractMenuItem, который реализует IMenuItem и является вспомогательным классом для создания экземпляров пунктов меню в различных частях.

ОБНОВЛЕНИЕ:

Что касается вашей проблемы с цветом, помогает ли эта ветка?

Не вставляйте MenuItem в DataTemplate. DataTemplate определяет содержимое MenuItem. Вместо этого укажите посторонние свойства для MenuItem через ItemContainerStyle:

<Menu>
    <Menu.ItemContainerStyle>
        <Style TargetType="MenuItem">
            <Setter Property="Header" Value="{Binding Title}"/>
            ...
        </Style>
    </Menu.ItemContainerStyle>
    <MenuItem 
        Header="Options" ItemsSource="{Binding ManageMenuPageItemViewModels}"
              ItemTemplate="{StaticResource MainMenuTemplate}"/>
</Menu>

Также обратите внимание на HierarchicalDataTemplates.

Вот как я делал свои меню. Возможно, это не совсем то, что вам нужно, но я думаю, что это довольно близко.

  <Style x:Key="SubmenuItemStyle" TargetType="MenuItem">
    <Setter Property="Header" Value="{Binding MenuName}"></Setter>
    <Setter Property="Command" Value="{Binding Path=MenuCommand}"/>
    <Setter Property="ItemsSource" Value="{Binding SubmenuItems}"></Setter>
  </Style>

  <DataTemplate DataType="{x:Type systemVM:TopMenuViewModel}" >
    <Menu>
      <MenuItem Header="{Binding MenuName}"         
                    ItemsSource="{Binding SubmenuItems}" 
                    ItemContainerStyle="{DynamicResource SubmenuItemStyle}" />
    </Menu>
  </DataTemplate>

    <Menu DockPanel.Dock="Top" ItemsSource="{Binding Menus}" />

TopMenuViewModel - это набор меню, которые будут отображаться в строке меню. Каждый из них содержит MenuName, которое будет отображаться, и коллекцию SubMenuItems, которую я установил как ItemsSource.

Я контролирую способ отображения SubMenuItems с помощью стиля SumMenuItemStyle. Каждый SubMenuItem имеет собственное свойство MenuName, свойство Command типа ICommand и, возможно, другую коллекцию SubMenuItems.

В результате я могу хранить всю информацию о меню в базе данных и динамически переключать, какие меню отображаются во время выполнения. Вся область элемента меню активна и отображается правильно.

Надеюсь это поможет.

Просто сделайте свой DataTemplate TextBlock (или, возможно, панелью стека со значком и TextBlock).