A Microsoft não anuncia nenhum programa que limpe automaticamente programas ausentes do registro. Então, se você não confia em terceiros, fica preso fazendo isso sozinho.
Se houver algum que você não possa remover, existem alguns utilitários da Microsoft aqui e aqui .
EDIT: Eu marquei esta resposta como Wiki da Comunidade porque percebo que isso não resolve o problema.