Um método que costuma resultar é entrares em modo de segurança, retirá-lo do arranque (se for o caso), e apagar.. sim, simplesmente apagar a directoria (a.k.a. "pasta") do programa.
Se souberes em que chaves do registry é que ele escreve, apaga-as (se não souberes saca um programa como o Regedit da sysinternals que ajuda bastante (não tenho links disponíveis neste momento)).
Toma cuidado àquilo que apagas, e usa bom senso. DLL's que o programa use, renomeia-os antes de os apagar, e se vires que não são necessários por mais nenhum programa, apaga-os definitivamente.
Normalmente, os que não trazem desinstalador são os que podem ser removidos manualmente
Podes sempre passar pelo Control Panel -> Add/Remove Programs, independentemente de não trazerem uninstaler, se ficarem no sistema, geralmente tens a opção de desinstalar pelo Cpanel.
Se assim não for, pode ser que sejam stand-alone e é só apagares.