Running MSIs shouldn't be a problem, including ones that require a reboot, assuming that after the reboot, they don't try to reboot again. (Most installers detect they're already installed the second time around and just return.)
Have you tried remoting into a VM and running the MSI manually? Often there will be a helpful error message. I assume the startup task is running elevated?
One random guess: is your app using osVersion="2"? osVersion="1" will give you IIS 7, I believe, and I think you need IIS 7.5.