Eu tive um problema semelhante depois que o Antivírus 2010 tentou se instalar em um dos computadores de trabalho de que cuido (eu digamos tentar, porque o usuário era um usuário limitado, então o Antivirus 2010 não pôde se instalar!).
Como Bobby mencionado, tente usar um programa antivírus ou anti-malware para verificar e limpar a infecção. Eu recomendo o programa Malwarebytes 'Anti-Malware .
O que acabei fazendo para impedir a exibição da caixa "Abrir com" (sempre que o usuário tentava abrir um link do Internet Explorer) criava um novo perfil.
De minha conta de administrador, copiei todos os dados que eles precisavam para manter (encontrados em C:\Documents and Settings\<username> ) em outra unidade.
Em seguida, usando a Ferramenta de perfis de usuário (clique com o botão direito do mouse em Meu computador, "Propriedades", guia Avançado, Botão "Configurações" na caixa Perfis de usuário), eu apaguei o perfil, criei um novo e copiei todos os documentos de volta.