Slightly different menus for different domains
Right. So I have written my own module to do what I wanted, using hook_form_menu_edit_item_alter() for configuration, and hook_translated_menu_link_alter() for displaying.

If anyone is interested in checking it out, initial dev version of the module is available in my sandbox here - http://drupal.org/sandbox/maciej.zgadzaj/1209152 - before I promote it to full project...

Edit:

Now promoted to full version available here: http://drupal.org/project/domain_menu_access