IMO The level of the cleaning action you use depends on how sluggish you think your PC is.
If there is one or two programs you think are dragging your PC into the dirt either as an anti-virus tool or something that has loaded itself into the registry then you might be able to use light cleaning utilities to fix the problems, software such as system mechanic, anti-spyware etc.
You might also want to check out the startup section of the registry as you might clean it but some perfectly legit software that you install are not rogue strings and can bloat the system, for example the older version of Musicmatch Jukebox that always used to load itself into the tray on windows startup, Winblinds etc. The is a free program called startup manager that I use to check out the startup section of the registry, but I don't have the link for now, I will re-edit and post later when I find it.
If you think there are several elements that are slowins down your system then reformat is the best way to go, no questions asked. If you are organised you could even make the reinstall progress as painless as possible by making sure you have essential software ready to install on another partition if you have enough disk space, and have a slipstreamed OS / Service Pack CD ready to deploy.
The choice as always is up to you, without looking at your system its hard to tell the best solution - but the rule of thumb is that if your only minorly bloated then you could probably clean the reg and programs and kill anything out of the startup cycle. If you are choaked then reformat.
