Well not all of them, but only those bound to WPF Commands.
After a 2 hour search, I finally found that a control that had focus, became invisible because it was not necessary anymore. Upon that event, my menuitems became grayed out (IsEnabled became false). Focussing a visible control on the screen resolved my issue.
So it seems that WPF Commands can not be executed when no focussed control is available.
