How do I fix the upgrade logic of a wix setup after changing InstallScope to "perMachine"

Sadly, the Windows Installer doesn't support that. Some process outside your package (a bootstrapper/chainer?) will have to manage the upgrade from per-user to per-machine.

Starting out with per-machine configuration.

<Property Id="ALLUSERS" Value="1" />

This will run an automatic per-machine check (if you have the MajorUpgrade element working, I presume), that does not pick up the previous per-user install:

Action start 15:46:35: FindRelatedProducts.
MSI (c) (D0:0C) [15:46:35:496]: FindRelatedProducts: current install is per-machine.  Related install for product '{0C6604FB-58EC-48B9-8259-5871EFDADEB9}' is per-user.  Skipping...
MSI (c) (D0:0C) [15:46:35:496]: FindRelatedProducts: current install is per-machine.  Related install for product '{0C6604FB-58EC-48B9-8259-5871EFDADEB9}' is per-user.  Skipping...

So before install, make sure you run another FindRelatedProducts call for products that have been installed in user scope (e.g. like this):

<!-- temporarily switch to per-user install scope-->   
<Publish Dialog="MyWelcomeDlg" Control="Next" Property="ALLUSERS" Value="{}">1</Publish>
<!-- find related products that have been installed per-user -->
<Publish Dialog="MyWelcomeDlg" Control="Next" Event="DoAction" Value="FindRelatedProducts">1</Publish>
<!-- switch back to per-machine install scope-->
<Publish Dialog="MyWelcomeDlg" Control="Next" Property="ALLUSERS" Value="1">1</Publish>

This in turn finds the per-user install:

Action start 15:46:36: FindRelatedProducts.
FindRelatedProducts: Found application: {0C6604FB-58EC-48B9-8259-5871EFDADEB9}
MSI (c) (D0:88) [15:46:36:716]: PROPERTY CHANGE: Adding WIX_UPGRADE_DETECTED property. Its value is '{0C6604FB-58EC-48B9-8259-5871EFDADEB9}'.
MSI (c) (D0:88) [15:46:36:716]: PROPERTY CHANGE: Adding MIGRATE property. Its value is '{0C6604FB-58EC-48B9-8259-5871EFDADEB9}'.

Existing products will be removed no matter in which check they are found.

Action start 15:46:41: RemoveExistingProducts.
RemoveExistingProducts: Application: {0C6604FB-58EC-48B9-8259-5871EFDADEB9}

On a side note: This does not circumvent a basic difficulty that arises when you have dual-purpose installers: User1 on the machine might install in per-user scope, then later User2 installs per-machine. User1 will see both installs in his programs/features table, and I do not know which one takes precedence. So consider going with per-machine installs only.