I use Registry Mechanic with Vista SP1 and I have had no problems.
The only thing I can suggest is that you use click here
Revo uninstaller is far better IMO than the Window's own add/remove program. Once you have installed Revo and you run it, you will then be shown a window that shows all your installed programs, if you left click (ONCE) on the Registry Mechanic program, next click the UNINSTALL tab at the top of the screen, you will then be shown a SELECT AN UN-INSTALL MODE window. You need to choose the ADVANCED OPTION (which is the bottom option).
After it has completed un-installing Registry Mechanic, it will then do a thorough search of your PC for any left over parts that relate to Registry Mechanic.
Once this has completed and you DELETE ONLY THE BOLD ENTRIES you then need to restart your PC and re-install Registry Mechanic.