Para vírus "básicos", você deve inicializar no modo de segurança e excluir o executável (você pode usar o Process Explorer ou o gerenciador de tarefas do Vista para localizar o arquivo), mas para tipos mais avançados eu sempre encontro usar o Autoruns da Sysinternal para remover sua capacidade de inicialização (junto com qualquer aplicativo auxiliar que eles possuírem) o faz. Qualquer coisa que sobreviva pode ser um pouco mais difícil de corrigir.