Quando esse tipo de coisa acontece, o computador fica em um estado inconsistente, no que diz respeito ao software (des) instalado.
Para resolver isso, o que eu normalmente faço é reinstalar o software ofensivo e, em seguida, desinstalá-lo novamente (com uma reinicialização intermediária para uma boa medida).
Devido ao grande número de aplicativos e seus variados instaladores, nenhum aplicativo pode gerenciar isso com segurança para você. Revo Uninstaller é muito bom para algumas coisas, mas se o registro não contém mais um registro de um programa instalado, você está sem sorte.