Our installer package always deploys new versions of our software as full package, without touching the already installed version. Users can run all versions of our sofware side-by-side. We need to have this option because of legal regulations in the business domain some of our customers are working in.
Other users would however prefer upgrading the existing version, they don't need the old version anymore and are not bound to these regulations.
How would you author such an installation package, if it is possible at all?
I must admit, I personally have not yet seen such an installer. Vendors seem to typically choose one route and stick with it.
You need two (more later) separate installs to do this. The basic difference between them is that one has an Upgrade table (that will do a major upgrade of the already-installed product, replacing it in Programs&Features), and the other won't have an Upgrade table, which means it's just another product being installed in the side-by-side scenario. In both cases they have a ProductCode that is different from all the installed Products.
You'd need a bootstrapper because I don't think you can do this any other way. The bootstrapper asks the user what to do and launches the choice of installs. You don't need two MSI files - you can have a single MSI with a transform (a .mst file) that deletes (or adds) the Upgrade table entries. You could use Orca on the MSI with the Upgrade table entries, delete the entries creating a transform. For the upgrade just launch the MSI file normally; for the side-by-side launch the MSI with a command line that includes TRANSFORMS=[mst file that deletes the upgrade table].
Of course you could do this with two separate MSI files, but you already appear to be up to your ears with multiple versions of MSI files and may prefer not to add more.
There may be a simpler alternative: It's the RemoveExistingProducts action that performs the uninstall of the older product. If there is a way for you detect (for example through a property value) that the user wants aside-by-side install then you could make the RemoveExistingProducts actions conditional on the property.