Export menu links with features
http://webwash.net/tutorials/import-and-export-menus-menu-import-module-drupal-7 shows how to use http://drupal.org/project/menu_import which uses path aliases instead of UUID.

I think this would work.