Yeah, NL could be making save states far more often. I was worried about the performance impact of doing them regularly when I implemented them. I never specifically tested the "is making more of them alright" angle; only the "does it give good enough results for backstepping".
Compression would make them less performant, which is a concern if they're being taken regularly. On the flipside though, regular save states - unless they're getting overwritten / discarded very frequently too (which may not be a bad idea) - will take up more memory. How well they'll compress is a concern too - it's likely only the physics maps and the visual terrain map that are actually worth compressing. The physics maps at least should compress very well. I don't know how necessary compression really is in NL's (or forks thereof) case, but if you did want to go down that road, it may also be worth looking into whether compression can be handled in a seperate thread.
The other thing I'd raise is that a very good idea is for the game's active state to also be a "saved state". NeoLemmix doesn't use such an approach because rewinding (and in turn, save states) were a later addition there; but in the case of Loap, which was built with this facility in mind from day one, the game's current state that gets updated by the engine each iteration, etc, is also an instance of the SavedState class (or whatever I named it). This helps to ensure that everything that needs to be part of the state, is part of it.