I had a similar issue with a client’s server, and the solution in their case was to increase the php max_input_vars setting in php.ini.
The number of menu items times the number of attributes for each item was exhausting the allowed input vars, so the server was silently truncating the request, resulting in menu items simply falling off the end.