Control menu item visibility
I have done something along these lines with custom blocks.  The basic approach is


Put everything you want in a menu, regardless of visibility
Make a custom block; make sure you don't cache it
In the render callback, get the menu $menu = menu_tree_all_data('menu-foo');
unset() any items in the $menu according to your visibility rules
Assign the items to $block['content']


Then you can assign the block to a region.