Instead of Your Uninstaller 7, I think we recommended Revo Uninstaller. They're both great. The main benefit of Revo is that it is free which everyone likes. I've used it plenty of times and it's worked pretty well.
Reformatting is just the sure way to make sure the problem will go away. Try to save it as a last resort because it takes times if you don't know how to image.
The VMWare idea is pretty cool with the snapshots and whatnot. Revert the snapshot to when you first formatted to make it brand new.
Bert has made plenty of excellent suggestions here. They're all good. Reformat would be the last option. The VMWare is a new way to handle things. It should save you a good bit of time in the future.