Você está executando uma ação personalizada em seu MSI que realiza a exclusão de atalhos? Nesse caso, a única maneira confiável que conheço é corrigir o produto instalado com uma atualização secundária do MSI para eliminar essa ação personalizada da execução na desinstalação. Quando esta atualização tiver sido instalada, você poderá desinstalar o produto e a ação personalizada do problema não deverá mais ser executada.
Em termos técnicos, a atualização secundária transformará o banco de dados MSI em cache no sistema para que a ação personalizada de desinstalação não seja executada. Isso é bastante complicado se você não tiver feito isso antes, mas é um "procedimento de trabalho". Tudo depende do seu nível de habilidade MSI.
Qual é o tamanho da sua base de usuários?