The first question I ask is why do you want to run a registry cleaner - what are the problems/symptoms you are suffering from?
My first action is to look at the programs installed (via control panel) and then uninstall all the clag I don't want/need. Reboot and see if that has made a difference. Then I would try a registry cleaner - I've used CCleaner in the past and it has improved the system, but I have had problems subsequently with MS Office updates and ended up having to repair the Office installation.
As Tom has suggeted, the best way is to back up your data, wipe the system and then reinstall from scratch. I would then install all the drivers, software, AV etc and make sure it is all up to date. Then I would carry out a system backup so that if you need to reinstall in the future you only need to run a restore. There is free software available that will do the system backup/restore and is actually built in to later versions of Windows. Also, some manufacturers (eg Dell) actually have a hidden partition on the hard disk that contains such a backup and using their software you can simply do a factory fresh installation.
Before retiring, when I was responsible for large numbers of computers, we used imaging software for all our computers so that reinstallation was a relatively quick and painless option and made setting up new 'standard' computers very simple.
The other suggestion of buying a new machine is the 'best', it depends on your finances and how much you value your own time. As with all this you need to decide what you want to use the machine for - does it do what you want effectively and efficiently - if so then stick with what you've got, if not then upgrade.
My old desktop was running XP and it slowed down so much as to be unusable. I tried a registry cleaner and it improved but it was never as stable as I liked. I reinstalled XP and it was so much better. As it was my second machine I then installed the Release Candidate version of Windows 7 after adding more cheap memory and couldn't believe how much better it ran - fast reliable - so I bought Windows 7 when released and have no regrets.
Misterfish