Sua configuração tem alguma ação personalizada? Se você especificou para verificar o código de erro, isso pode acionar a reversão da instalação e da desinstalação.
A desinstalação está realmente completa ou será revertida deixando o aplicativo ainda instalado?
Nos casos em que uma desinstalação falha para um produto que está em estado natural, a solução normalmente é desenvolver uma atualização secundária para o MSI e entregá-lo como um patch. Uma atualização secundária realmente altera o banco de dados de instalação em cache no sistema e, portanto, você pode corrigir quaisquer erros na sequência de desinstalação. Então você executa a seqüência de desinstalação normal depois. Isto é ao contrário de uma atualização importante que é essencialmente uma desinstalação do produto existente e uma reinstalação. Criar tal patch é um pouco trabalhoso e bastante complicado. Se o aplicativo não estiver "em estado selvagem", normalmente acabo zapping a instalação usando MsiZap.exe do SDK do MSI e, em seguida, resolvo os erros no MSI antes de testar novamente.