It really sounds like your registry has been damaged beyond repair from the software you were using to "clean" it. I still strongly advise a clean install. If you are still reluctant, you could try an in-place upgrade install (repair install) of Windows. The in-place upgrade will keep your programs and user files intact and just replace Windows components.
If your programs were also damaged within the registry, though, an upgrade install will still require those programs to be re-installed. The upgrade install is not guaranteed to fix all registry related problems, whereas the clean install would be.