Further to the puzzle,
after a few edits to other pages the order in the admin panel changes as well. I'm thinking I don't quite understand whether there's some kind of a "refresh" going on that weirdly reorders menus...? Do they reorder themselves according to what was published last?
Any help appreciated!
To be safe, try adding /?flush=1 to the end of your URL, though I doubt that's the problem.
Also, when you create and order new pages, you have to go into that page and save and publish it. If you drag and drop the page around in the tree, you still have to go in and save/publish the page for it to show up in the menu.
Not really sure what else it could be. Never experienced that problem.