@mcmanimal, your solution (almost) worked for me. On my wife's laptop with Win 7 I tried many other things, but to no avail. There was a snag, however, merely renaming the folder from Hirens resulted with something odd - Windows recognised folder name change, and adjusted shortcuts accordingly (!) so I started Hirens again and deleted it from there. It did it.
After cleaning the remains in ccleaner, it couldn't delete two registry entries, so I tried it manually. No success. Even after attacking them from regedit running as system - nothing. Thank God viruses are not this resilient.

I have no idea why I couldn't uninstall it "normal way". I was OK with it to the point it couldn't be updated for a "different language installation" problem, and first I tried few possible languages it could have been installed from. I even tried reinstalling the original version that was still there in a "downloads" folder, but nothing happened. So it had to go.