This is a bit late but I just re-created your situation, created a complex object, then smoothed and deleted the history. Undo works fine. Also, like Ahnslaught mentioned, sometimes the hotkey doesn't work and you have to do it via the edit menu. Now, if you closed out your project then tried to do it after re-opening, you're obviously going to be out of luck.

A couple of future suggestions would be to a) go into the preferences and increase the number of undos (to like 50 or so) and b) in the file > save scene dialog box, tick the incremental save box and make the number whatever you want. Now, each time you save, maya will create a new file (up until you reach the limit you specified). This way you have files you can go back to if you mess up along the way (or if something gets corrupt, somehow).