It's somewhat my fault but I think it's not such an uncommon scenario.
I had installed 2.7.10 x64 some time ago into C:\Python27_64 but then had to delete it to save space. Rather foolishly instead of using the uninstaller, I just trashed the directory and now I have a problem: neither the Control Panel uninstall item, nor the fresh 2.7.12 installer work. The latter fails when it tries to use the nonexisting Python to remove pip:
--------------------------------
MSI (s) (04:B0) [11:00:09:881]: Product: Python 2.7.10 (64-bit) -- Error 1721. There is a problem with this Windows Installer package. A program required for this install to complete could not be run. Contact your support personnel or package vendor. Action: RemovePip, location: C:\Python27_64\python.exe, command: -B -m ensurepip._uninstall 
--------------------------------
In the UI just the first message is shown, without the failed commandline, so it's not at all clear what went wrong.

I think at the very least the user should be informed about the failed command so they can clean up the old installer's remains, or maybe the installation should be allowed to proceed anyway, replacing the bad paths in the registry.

In the end, I had to use "Msizap TWA {E2B51919-207A-43EB-AE78-733F9C6797C3}" after which I could install 2.7.12 into a separate directory