Undo system in object mode is so called “global undo”. Which is, basically, equivalent of saving current .blend file in memory (a bit smarter than, since the undo memory de-duplication system is in place). So when you undo Blender tosses away current .blend file state and opens a new one from memory, causing every object to be re-evaluated since their evaluated state is lost.
In edit mode (and other modes like painting, sculpting, etc) the undo system is more localized, and only stores changes for a specific object or its parts. Undo in this case will only restore state of a single object and re-evaluate that specific object.
One of the possible solutions would be to somehow preserve evaluated status through global undo steps as well. This isn’t a small project, but, hopefully, will be tackled as part of a project related on improving Blender for handling large and complex scenes.
Confusing part to me here is that you mention that if undo brings you back to an edit mode, the undo is still slow. This isn’t something what i would expect. Worth isolating and making a report i’d say.
P.S. Campbell is more familiar with the nowadays’ undo system.