Based on that, I would guess that something was corrupting the menu configuration as it was being stored in or read from the database. Maybe something that tries to filter/update the site URLs or replace some keywords?
Longer explanation:
When you enable the compression option, the plugin still stores the same configuration in the same place in the database, except it’s converted to a compressed format. So if there was a DB issue (e.g. a corrupted table) or a general plugin bug that prevents settings from being saved, turning on compression probably wouldn’t change anything. The fact that it helps suggests that it matters what exactly gets stored in the DB.
The most common way for menu settings to be lost/reset is that there’s some plugin or tool that tries to blindly search-and-replace text in the database, e.g. to update the domain name after site migration. In principle, instead of doing that in a single pass, a plugin could do something similar dynamically as data is being read/written to the DB. Compressed menu configuration data is not human-readable and would no longer match searches like that.
