O executável fica onde está, o problema é causado pelo "atalho" ser um atalho especial do Windows Installer que executa o executável principal associado ao pacote instalado. O que, como você diz, significa que ele quebra sempre que o pacote instalado é substituído.
Um simples atalho criado manualmente para o executável real deve funcionar bem.