Uma reinstalação completa é a opção mais segura - é a única maneira de você ter 100% de certeza de que o sistema estará limpo.
Mas, se você está tentando evitar isso, a maneira mais eficaz de limpar um sistema é inicializar um Live CD / USB, para que o malware não tenha a chance de ser executado e executar todas as tarefas de limpeza de lá. Nesse caso, eu recomendo esta pergunta como fornece algumas boas opções para Live CD's para esse propósito.
Além disso, você pode encontrar esta questão para ser útil, uma vez que discute onde a infecção pode ter vindo.