Hmm, that might not be easy via a forum post.
Might require manually editing the registry. Give ol' CCleaner a try first. You might have had a failed uninstall leading to the problem at some point. One option there is to re-install that exact version that won't uninstall directly from Microsoft, it should prompt you to perform a repair. Then you can try removing it again, or running your game.
If that doesn't work, safest bet might be an in place Windows install (AKA install windows and keep all my files) You'll lose basic settings and your installed programs might no longer be registered, but it should work. If you are up for a fresh install never hurts, just make sure to back up everything you want to keep.