Basicamente, você tem um instalador mal projetado.
O que você poderia tentar é definir a propriedade ALLUSERS na tabela de propriedades como 1 (usando o Orca, procure por Orca.msi no SDK do Windows Installer ) que forçará uma instalação por máquina.
Nesse caso, o instalador solicitará a elevação parcial durante a instalação ( é assim O UAC + MSI deve funcionar e você deve estar bem.