since your'e planning to do this via ad and gpo and with msi, add a package install for the new package, and in that add a script for removal, or even better, add the uninstallation of the old package in the new one.