Whilst having a team of consultants and sales staff under my wing we used to re-install all Windows machines annually. The effect on performance was always staggering as users have generally no idea how much 'occasional' software has been installed over the last year and even though uninstalled, it always leaves a mark.
We tried a number of registry cleaners, some free, some purchased and never experienced the same results. Yes, a re-install took a while but with a bit of planning and a CD will all your favourite installs and drivers saved on it, it was never that bad and worth the extra time.
Today, I never recommend 'clean-up' software but do tell my clients not to install software unless they really need it and to avoid 'trial' software if at all possible.
I also tell them not to install printer software as this can be a major cause of PC performance issues. All you really need are the drivers.