Hi There,
What I would first try is to use the built-in MSI functionality for removing previous versions--the Upgrade table.
Basically, you can create a new transform and insert entries into the Upgrade Table using Direct Editor, putting in the Upgrade codes for each previous version (or a single entry, in the case that they all share the same upgrade code). You get these upgrade codes by opening the MSI files in InstallShield or Orca, and looking at the Property table for the UpgradeCode property value.
As for a reboot, just navigate to the Installation Designer -> Custom Actions and Sequences -> Installation -> Execute, and right click on RemoveExistingProducts and select "Insert".
Then you'll choose to insert a Standard Action, and select ForceReboot.
If all goes well, using this *.mst file will do what you are looking for. But, of course, there's a lot that can go wrong, including a lot of things that are out of your hands -- the software vendor may not have designed their packages to be uninstalled in this fashion. So if you run into problems, I would give this a read first and see if it helps:
Major Upgrades
http://msdn.microsoft.com/en-us/library/aa369786(v=vs.85).aspxQ113394: HOWTO: Troubleshooting Major Upgrades
http://kb.flexerasoftware.com/selfservice/viewContent.do?externalId=Q113394And lastly, remember to log everything!
How to enable Windows Installer logging
http://support.microsoft.com/kb/223300