Not much of an answer but I was able to work around this using the Loaded event and setting the the Icons image in the handler.
    void MenuItem_OnLoaded(object sender, RoutedEventArgs e)
    {
        var menuItem = (MenuItem)sender;
        if (menuItem.DataContext is OptionMenuItemViewModel x)
            menuItem.Icon = new Image { Source = new BitmapImage(x.ImageUri) };
    }
With the following XMAL
    <MenuItem Header="_Database" ItemsSource="{Binding DataBaseMenuItemViewModels}" >
                <MenuItem.ItemContainerStyle >
                    <Style TargetType="MenuItem" >
                        <EventSetter Event="Loaded" Handler="MenuItem_OnLoaded"/>
                        <Setter Property="Header" Value="{Binding Path=Title}" />
                        <Setter Property="ToolTip" Value="{Binding Path=ToolTip}" />
                        <Setter Property="Command" Value="{Binding Path=Command}" />
                        <Setter Property="CommandParameter" Value="{Binding Path=Message}" />
                    </Style>
                </MenuItem.ItemContainerStyle>
            </MenuItem>
However, I sure would like to know why the obvious didn't work.