Eu consertei um computador de amigos com sintomas parecidos - a causa acabou sendo um rootkit que estava sendo inicializado a partir de uma partição oculta de 20MB no fim da unidade.
O rootkit estava recebendo controle quando a máquina inicializava e, por sua vez, estava inicializando o sistema operacional legítimo e hospedando-o. Longos tempos de desligamento da máquina foram resultado do malware, permitindo que os processos sejam concluídos antes de continuar o desligamento.
Terminou a nuking toda a unidade - incluindo a tabela de partições, e começando do zero com uma nova instalação do sistema operacional.
Valeria a pena conferir as partições no seu disco para garantir que apenas as legítimas estejam lá.
Uma observação: no meu caso, a partição de malware foi marcada como oculta e não apareceu na maioria das ferramentas de partição; Eu tropecei nele ao usar um live-cd do Linux para fazer uma varredura de malware.
PS: Eu realmente espero que isso não seja a solução para o seu problema, já que a remoção desse tipo de malware é tediosa e desagradável.