Isso acontece com programas cujo o desinstalador não é tão eficaz e não funciona corretamente, deixando resquícios do programa que você não necessita mais em seu PC.
Para solucionar esse problema, você pode editar o registro do Windows, indo até HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Uninstall.
Chegando nesse ponto, você procura a "chave" responsável pelo programa que não existe mais e a exclua.
Lembrando que o Registro do Windows não é brincadeira e que deve tomar cuidado caso não esteja familiarizado com ele. Recomendo que seja feito um backup dele antes de realizar qualquer alteração caso não tenha familiaridade com o mesmo.
Para realizar o backup, no Registro do Windows clique em Arquivo > Exportar. Na opção "intervalo de Importação", selecione "Tudo" e salve-o em uma pasta de fácil acesso em caso de necessidade no futuro.
Abraço!
