Menu item path saved as node/nid instead of alias An alias supplied to the [Path] attribute of a Menu Link is converted to node/nid when saved, (along with a nice message: "The menu system stores system paths only, but will use the URL alias for display".)   This is implemented in core: function menu_edit_item_validate of menu.admin.inc.   (Drupal 7.22)

When moving nodes around between instances of the same site with node-export and uuid, node/nid is no longer valid, and results in menu links being dropped, or pointing to the wrong node.  

A similar question was raised earlier:

How do I use URL aliases in menus?

But the solutions I think are for different use cases.  The suggestion of adding the alias and menu item together on node creation does not seem to work.   Our concern has nothing to do with how the node url is displayed.

UUID_path or maybe UUID_features seem to imply a solution, but if there is a resolution there, I don't understand it, and will appreciate any insight into how to handle this.  

In the end, we need to have exportable menu links with path attributes that, one way or another stay, linked to an alias, regardless of nid.
Both nid and aliases are not guaranteed to be stable and unchanged, nid being a bit less prone to mutation. What you seem to really need, are UUID Links. It should allow you to store links by the unchangeable UUID, not localised nid.

There was also a sandbox project UUID Menu for just the case, but it seems it was never properly initiated.

The other approach is to export both content and menu as a Feature. This problem is in Features' issue queue and in UUIDs for Menu Links issue queue, unresolved yet. But in the second one patches exists.