O atalho deve ter sido corrompido de alguma forma. Fazer um novo atalho como você fez é uma solução perfeitamente boa.
O pai das amigas me ligou por não conseguir abrir o Internet Explorer, então fiz a seguinte depuração via Remote Desktop.
Clicar no bloco envia para a área de trabalho e o Internet Explorer não é aberto (nem mesmo no Gerenciador de Tarefas).
Ao pesquisar por "Internet Explorer", um único bloco de aplicativo é mostrado com o logotipo do IE e o texto "ms-resource: TileDisplayName".
Consegui isso fixando C:\Program Files\Internet Explorer\iexplore.exe em Iniciar e Área de Trabalho, o que é uma boa rodada de trabalho, mas estou interessado em saber por que isso teria ocorrido e como alguém iria reparar isso ...
O atalho deve ter sido corrompido de alguma forma. Fazer um novo atalho como você fez é uma solução perfeitamente boa.