When this sort of thing happens, your computer is left in an inconsistent state, as far as the (un)installed software is concerned.
To resolve this, what I normally do is reinstall the offending software, then uninstall it again (with a reboot in between for good measure).
Owing to the massive number of applications and their varied installers out there, no single application can manage this safely for you. Revo Uninstaller is pretty good for some things, but if the registry no longer contains a record of an installed program, you're out of luck.