I had a similar problem.
Only solution was find the install folder, then completely uninstall. The install folder is still there, along with some settings files, so I had to delete everything that was left before I could re-install.
Actually, the uninstaller for the game is quite un-thorough. Not a super-important bug for the game in general, but it does create situations like these.