A maioria dos programas apenas remove a entrada de registro do registro, eu uso AutoRuns para ver especificamente onde eles correm no registro, há muitos locais onde programas podem ser executados no registro.
Como teste, usei Auto runs para ver onde um software de inicialização que adicionei é executado a partir de (HddLed), abri o editor de registro e com certeza estava lá, desmarcando a caixa ao lado do item de inicialização no Autoruns e atualizando a exibição do registro, a entrada foi embora. Voltei para o Autoruns e marquei novamente, e a entrada retornou.
Suponho que outro software possa usar outros métodos para realizar a mesma coisa, mas esse é o método mais comum.
Antes
.
depois
Aqui é onde o software específico que eu adicionei é executado no registro.
HKCU\Software\Microsoft\Windows\CurrentVersion\Run