I still use Ccleaner regularly. It is very good, is regularly updated and is free. As you may know from Adobe Forums: My favorite tools I also use Perfect Disk, which also includes a registry cleaner and often these programs find different issues, like one is looking under the kitchen sink and the other under the sideboard. Both are good, but when installing and as you expressed you want to have a backup of your clean install, well as clean is possible with Windows by itself, you can use Regedit to create a backup of your current registry file, or you can use this tool, which is the best registry cleaner I know, but it is not free: http://www.1clickpcfix.com/
I think it makes no difference for 1ClickPCFix whether you run it before installation or after, because it looks at the consistency of all the entires in your registry and it does a very thorough job. It takes some time, but it easily finds more inconsistencies than CCleaner or Perfect Disk. I highly recomment it.
I use Ccleaner regularly and it has always been the best application of it's type for me. (Although I am now going to look at Harm's favorites as well)
I don't think that installing these programs before or after you install applications makes much difference. Ccleaner does not run in the background. It only scours the registry once it is launched.
I use CCleaner for general cleaning, but I use Eusing for registry cleaning:
It automatically makes a backup of the registry, although I've never had to use the backup.
Try Registry Recycler. I have recently come across it and found it a great subtitute of CCleaner. CCleaner is my first choice but it is not free anymore which is why i now prefer RR. Its free and does well in order to find and fix my registry errors. Here is the Download Link: http://www.freewarefiles.com/Registry-Recycler_program_84479.html
CCleaner is still free. You can pay for a "pro" version with priority support, but the free version is still available.