A family of Microsoft relational database management systems designed for ease of use.
I had this same problem and found when I went to exit Visio it said that I had a large amount of data in the clipboard (because I had just created a multiple tabbed document with pastes from multiple individual files). So once I agreed to clear the memory and then logged back into my Visio file, my undo functionality started functioning as normal. So in my instance a simple restart fixed it... hopefully you resolved your problem in a similar manner as I would hope anyone reading this thread could try the same.