The WordPress menu items limit is a tricky problem which we've only seen twice before. The most recent was a few days ago, one of our clients with a rather large WordPress site started losing her menu items. It started suddenly and for no apparent reason. She started losing menu items after adding a new one. In fact the entire menu would disappear and she would have to recreate the entire menu and save it.
Then as soon as a new page or post was created and that item was added to the menu, the entire menu would disappear. She would then have to recreate the menu (once) again. With a small number of menu items this may take a minute or two to do but with large menus it's a nightmare. Add to that nested menu items and you have a disaster.
As mentioned earlier, it's a tricky one as her menu length was about 40 items, the previous time we saw this the menu items was a bit more, it was over 60. There seems to be no fixed point at which this could occur. According to a WP Beginner article referring to the same problem, they tried to recreate the problem going as high as 200 menu items without replicating the menu limit error. So it's really all over the place.
So it seems it's a combination of WordPress and PHP. There are Suhosin limitations on the POST max variables that are limiting larger numbers of entries from being saved. It's a security precaution that can help prevent DoS attacks. You can read a more complete explanation here on SevenPark.
The quickest solution is to simply add a line to your php.ini file like so:
And that's it, you should have no further lost WordPress menus.