Acontece que acabou sendo um problema com um utilitário de licenciamento de terceiros que é instalado durante o processo de instalação. A questão de fato estava presente apenas em máquinas com o Windows Installer 4.5, mas a atualização do software de terceiros para a versão mais recente "corrigiu" o problema.
Não tenho certeza de como o WI 4.5 poderia ter causado isso, já que o instalador de terceiros não usa o Windows Installer, mas acho que é isso que você obtém quando usa software de 4 anos porque a empresa não quer pagar por um upgrade, haha.