Eu estaria executando o Microsoft SysInternals Process Monitor no modo de registro de inicialização para ver onde o atrasos são (use a coluna Duração ).
Além disso, qualquer coisa no log de eventos do sistema? Além disso, verifique o sistema de arquivos em busca de arquivos de log (msi * .log e appmgmt.log).
Por fim, verifique o registro de um dos clientes. Não me lembro da localização, mas os MSIs instalados mantêm sua origem de instalação UNC. Há uma chance de que o Windows Installer esteja tentando localizar o código de desinstalação do UNC original. O monitor de processo também deve mostrar isso. Se não, faça um rastreio wireshark.