As there's already a wiki regarding cleanup tools, are there any tools that have given you negative results (i.e. made the system worse)?
CCleaner is a good and simple tool for PC cleanup.
I'm assuming you're talking about Windows here, since you tagged this with antivirus, malware, spyware, etc.
Personally, I use AVG Free, Avira Antivirus, ESET NOD32, Superantispyware, Malwarebytes AntiMalware, Spybot S&D, and Lavasoft AdAwawre. No negative effects with any of them.
In addition, on new computers, I run PC Decrapifier, just to get rid of the bs that comes on new computers these days. If this is at work, though, I will just reimage the computer completely.
If we're talking a corporate system, time is money. I have generally found that running clean-up tools takes longer than it would to re-image the system. Also, you can never quite be sure if you got rid of everything, which is not good in a corporate environment. From a security perspective, blowing the system away and re-installing it is really the only good option.
With that said, and to your question, I have seen the Symantec tools have an issue with Spybot (this has been well reported) and I consider that obviously an issue. I have seen folks running the scans not understanding the results and doing things detrimental to the system (like making the changes to the registry that shouldn't be made) but generally the more commonly recommended tools have been rock-solid for me (Spybot S&D, LavaSoft AdAware, etc.). I steer clear from the others without a proven reputation because there are plenty of horror stories out there.
Offline Virusscan with WindowsPE or Knoppix
Systemstart cleanup with Autoruns
or finally a fresh install
Virus scanners? As discussed in the answer to your similar question, I don't worry about "cleanup" as such. Life's too short and both myself and our users are too busy.
Doesn't matter how good your local hospital emergency room is, it's always better not to need it in the first place.
As for the virus scanners we use to prevent infection... We used to use F-Secure Antivirus and we've recently switched to Kaspersky AntiVirus for file scanning and the like on our LAN. These both can be centrally managed, updated, configured, etc. and that is just what we want.
Spysweeper is by far the best malware cleanup tool I have come across. I have been using it for years and I recommend it to all my personal clients. I do a lot of sidework fixing machines for home users, and I've seen spysweeper do amazing things. In addition to sweeps, spysweeper has active shields watching your system so if bad things try to get on there, spysweeper has a good shot at catching some things before they even get on the system.
Spysweeper by webroot does not come in a huge bulky suite of apps like the Norton's and Mcafee's that tend to take up a lot of system resources or annoy you with all kinds of popups asking you if you want to allow stuff. Spysweeper is less heavy, and just does it's thing in the background unless it wants to tell you something bad is trying to happen. It has only gotten better as time has gone on.
Blowing away a system and starting over is sometimes a good idea, however going forward you need a good tool to keep your system clean so that you don't end up blowing it away in a few months for the same reason.
I have also come across Smart Defrag recently, it is an excellent free defrag tool that's more rebust than the built in windows defrag tool. You can schedule defrags, and autodefrag can run in the background and defrag your system whenever it is idle. I've actually started using it at work on my windows servers, do check it out it's a great tool
In a corporate environment, setup an automated package installer, like WPKG, in combination with a cloning system, Clonezilla, or unattended installer.
Backup data, format, reinstall, setup user profile with backed up data. Much much much faster than figuring out what every little virus is(i always seemed to get unremovable items, there are some nasty new viruses that our people always seem to get, damn porn sites/stupid users wont stick to redtube!)
I prefer ComboFix but can occasionly remove things that will end up hosing the system. The good news it will either fix the issue, or put you in the re-image scenario in under 10 minutes.