Have you tried cleaning the registry manually?
I could not reinstall SH3 into my Windows 7 recently and what helped was actually using regedit and search function. I found an SH3 line there that automatic registry cleaners had not found.
(I also found a line about Civilization IV Colonization and deleted that as well, as I had not been successful in reinstalling that game).
That helped with both games - and now I'm knocking on wood and stuffing my pockets with hare legs in hope that the games might stay operational on my computer for awhile. The biggest reason I haven't bought a faster computer is the hassle of trying to make SH3 etc essential programs working on the new one. But that is another subject.
Try manual editing if you haven't already
