Export menu as feature?
You need some way to assign UUIDs to menu links. Just like how the uuid_features module assigns UUIDs to nodes. 

For Drupal 6, there's a patch to the uuid_features module that has worked well for me. (See comment #2 on the issue for instructions.) 

Haven't tried for Drupal 7.