Recently we ran into a bug in WordPress that when we tried to save one of our very large menus it was being truncated and then saved. Luckily we had a very recent backup and recovered and then I did some investigation.
What I found was that our server had upgraded from PHP 5.3.5 to latest stable 5.3. PHP added a new runtime variable max_input_vars (default 1000) in 5.3.9, which we went past during the PHP upgrade. This variable was introduced for good reasons — “Use of this directive mitigates the possibility of denial of service attacks which use hash collisions.” – from PHP.net.
Unfortunately, very large WordPress menus can have over 1000 input elements and during a save it appears they all get submitted. So, our large menu, which we estimated had about 1300-1400 input elements got truncated to about 2/3rds of its size.
Well, you could, and probably should reduce the size of the menu. Or, up the value of max_input_vars to be large enough to handle your menu size, plus enough extra to future-proof it somewhat. Obviously the second option opens you up to a potential DoS.
If you are using the Suhosin patch then you might want to read this article.