A couple of loose ends to tie up, perhaps:
- I would advise against use of any registry cleaner - the potential to trash your system is far, far greater than any benefit.
- If your OS key doesn't authenticate correctly online after the reinstall, use the automated phone system method. It works a treat.