Esta publicação no fórum sugere que desabilitar o comando Executar como em O Explorer também irá corrigir o comportamento que você não gosta. Parece um pouco confuso, já que também removerá o comando Executar como no Explorer para uso legítimo.
É mais provável que as chaves de registro para executar arquivos EXE tenham sido danificadas. Eu acredito que você deseja restaurar HKEY_CLASSES_ROOT \ exefile \ e é sub chaves para a informação correta. Este artigo sugere algumas maneiras de fazer isso. AVISO: Eu não tentei isso e não sei se as informações no artigo estão corretas. A pesquisa por HKEY_CLASSES_ROOT \ exefile produzirá vários outros artigos e postagens no fórum que soam como seu problema. Mais uma vez, não sei se a informação está correta.
Você também pode comparar essas chaves de registro em relação a um bom PC conhecido. Talvez haja apenas um ou dois que precisam de ajustes para corrigir o problema.
Sempre faça o backup do registro antes de fazer alterações. Salve o backup em algum lugar que não esteja no PC que você está tentando consertar, apenas no caso.