How to share a menu across more website
I think the idea of using a feed is an attractive one. I don't think there's any way to push a menu definition out as a feed using existing modules, though.

I'd write a very simple module to provide a single callback that would fetch the menu definition and theme it as xml or json (easier). That could then be fetched at intervals by your other sites.