I don't know whether this idea is acceptable, I can think of some reasons it might not be, but you do have the option of writing that uninstall string to
Scheduling a reboot at the end of the install will remove the product for you.
Another idea which might work, though I'm not entirely convinced, would be to run the Uninstall String in a CA after InstallFinalize (and not allowing the installer to wait for it to finish).
But are you sure you can't use the upgrade table? I thought all MSI installers had an Upgrade Code.