Não é um problema díficil de resolver, mas até descobrir, confesso que também entrei em stress.
Vamos por partes:
Primeiro faz o download da chave de registo que te vai ajudar a ultrapassar o problema, em
http://www.kellys-korner-xp.com/xp_tweaks.htm ( é o ficheiro da linha 12 ).
Executa-o, adiciona a chave ao registo sem medos.
De seguida, vais a Ferramentas -» Opções de Pasta -» Tipos de ficheiro ( axo eu..tenho isto em inglês , é o 3º tab ). Aí clicas em "New" ou "Novo" e adicionas a extensão EXE (não necessitas de colocar o ponto atrás ). Clicas em Avançadas e associas a "Aplicações" ou "Applications ".
Repetes o processo para a extensão LNK e associas a atalhos ou links. No final, dás OK --» Aplicar e reinicias.
Se tudo isto não der resultado, inverte a ordem dos processos, ou seja, primeiro associas as extensões e só depois adicionas a chave de registo. ( Já não me recordo bem, como fiz na altura ).
Boa Sorte, dps diz se resultou.
PS: Á partida não é vírus, comigo desconfio que foi algo que o AD-Aware, alterou inadvertidamente, por acaso tens este programa instalado ?
Cumps !