R – VS2005 Setup and Deployment – MSI Installer on reboot

RemoveExistingProducts before InstallInitialize or after InstallFinalize will not put the Action in the audit script of the new product, so as you said the old product is removed before the Upgrade is done.

So you might want to try to put the RemoveExisitngProducts execution between InstallInitialize and InstallFinalize, that way it's in the remove is in the audit scripted part, so it will track, the reboot and resume.

have a look at the system reboot properties here

Is it possible that prior to the reboot one of the installed files has been modified for some reason?

I'm not familiar with the error message, but perhaps Windows installer is attempting to repair the installation on reboot?

Have you tried installing the product once, then prior to rebooting running the installer again and selecting the repair option and seeing if this succeeds? If the repair fails at this point, run it again from the command line with verbose logging turned on:

msiexec /lv logfile.txt /i "MyInstaller.msi"

and when the error message pops up check out the last thing to happen in the log file.