Oleg,
Based on other questions you've asked I understand the jam that you are in. It's unfortunate but there isn't much you can do. You could wrap the MSI in a bootstrapper (EXE) to remove any existing Per-User installation for the person logged in ( assuming it wasn't pushed to the machine using the SYSTEM account ) but that wouldn't handle a situation where some other user profile had installed the app.
Here is about the best thing I can think of for your situation. Create your new installer to install to a new directory and new registry keys ( completely different foot print then your old application ). Give this new MSI a fresh UpgradeCode property. Author an active setup registry key to run a cleanup utility the next time a user logs on and then reboot the machine. Put the old UpgradeCode in the Upgrade table just in case you can get lucky for an old per-machine install.
When someone logs in for the first time your EXE will be run. It can then perform MSI API queries to look for old versions of your product and perform an uninstall. In time your old application will be removed.
I recall getting myself into this situations many years ago before I understood the ALLUSERS property. Per-User installations are a pain and only useful for non-privlidged "viral" (as in socially spread) application. It's not a good story for commercial / enterprise applications.