Managed to solve it with the following (eventually the Header is bound instead of the Visibility, but is irrelevant regarding the solution):
1) Separating the menu into a separate static resource:
<collections:ArrayList x:Key="mnuToggleFlag" x:Shared="False">
<MenuItem Command="local:MainWindow.ToggleFlag"
Header="{Binding Path=Flagged, Mode=OneWay,
Converter={StaticResource flaggedToHeaderConverter}}" />
</collections:ArrayList>
2) Referencing it from the ContextMenu:
<ContextMenu x:Key="mnuContextTreeView">
<ContextMenu.ItemsSource>
<CompositeCollection>
<CollectionContainer Collection="{StaticResource mnuRun}" />
<Separator />
<CollectionContainer Collection="{StaticResource mnuResults}" />
<Separator />
<!-- Below is the reference for the new static resource -->
<CollectionContainer Collection="{StaticResource mnuToggleFlag}" />
<CollectionContainer Collection="{StaticResource mnuStandardEdit}" />
</CompositeCollection>
</ContextMenu.ItemsSource>
</ContextMenu>
3) Setting DataContext from the code behind:
((MenuItem)((ArrayList)Resources["mnuToggleFlag"])[0]).DataContext = _actualItem;