The undo history does have some issues. If you ever notice specific steps that never undo, or always undo in the wrong order, please report it. Also, keep in mind you can always open the History panel.
Also, there is a preference that automatically clears the undo history anytime levels save. So if auto-save is running, your undo history is going to reset every time auto-save runs. It sounds like this is a different issue, but you can turn off that preference in case it helps.
I'm curious - does clearing the cache folder have any impact if the undo command stops working?