Não foi bonito, mas resolvi isso sozinho procurando manualmente todas as referências ao meu produto no registro e excluindo essas chaves. Eu também mudei minha instalação para por máquina (por enquanto) para forçar a elevação para instalação e desinstalação.
Eu ainda apreciaria uma solução que não envolve mexer com o registro se houver, apenas para referência futura.