Credo como isto vai
Bem sobre o facto de mesmo após a desinstalação de software ficar sempre muito "lixo" infelizmente é um fardo que todos temos que encarar,pois devido a falhas dos S.O's e da programação dos softwares,ficam sempre alguns "restos" que vão encalhando os Pc's(ficam mais lentos com o tempo)e ás vezes até dão problemas de maior(BSODS,Probs a instalar software etc etc...
Bem a melhor forma ou pelo menos a maneira que eu costumo fazer é,depois de desinstalar os programas k n interessam,verifico na pasta Programas,se n fica pra lá nenhum "apêndice",e apago-o obviamente.
Depois uso alguns programas de manutenção/limpeza do S.O tipo:
http://www.ccleaner.com/download/
ou
http://www.velasco.com.br/projmvregclean.htm
apenas exemplos,que ajudam a limpar detritos k vão ficando.
Há casos,que mesmo após estas limpezas alguns ficheiros continuam no Pc e causam problemas,geralmente apagando-os manualmente do Registo(
http://support.microsoft.com/kb/256986/pt )costumo resolver mas apenas aconselho a quem conhecer o k está a fazer
Resumindo,não precisas de formatar o Pc(pelo menos já

)apenas vai dando uma boa manutenção com os progs k mencionei em cima,apagas as pastas k ficarem e tá tudo
Cumps