damn...
I guess then it's time for something a little more in depth.
Ideally you setup a virtual machine
and get procmon
http://live.sysinternals.com/procmon.exe
If the setup in question does a per user installation, a new user profile might be sufficent, so maybe try that first.
Start procmon and let it record all registry activity from the setup in question, then run the setup on the virtual machine, if all goes well, the setup should be able to install the programm.
With the protocol from procmon you should then be able to figure out which keys and values are created by the setup and clean any that still remain on your physical machine out of the registry.
Before you start cleaning I would highly recommend that you create a restore point, just in case anything goes wrong.