Unfortunately, the Windows installer does not support upgrading "across contexts". As you found a per-machine package cannot upgrade a per-user package and a per-user package cannot upgraded a per-machine package.
You could write an executable that finds the old .msi and uninstalls them using APIs like ::MsiEnumRelatedProducts()
to find the products and then ::MsiConfigureProduct()
to remove them. However, without the user account, I'm not sure you'll be able to see the per-user installed product.