It actually depends a lot on the malware in question as to whether a removal tool is in fact a really feasible option. Whether said tool works or not depends on how much the author of the tool knew about the original malware and what it did.
To illustrate my point, take a look at something like Autoruns. There are a whole slew of ways to get your chosen executable to run on windows startup which autotools mostly displays, but only two of those are standard choices for the average software engineer. Malware authors can easily use many of the other areas, or even multiple areas, to become much more persistent across reboots.
Next up is the damage you can to the windows registry. For example, the handling of
.exe files is in fact denoted by a registry entry, so there's an attack point with which I could damage your system if you undid it naively. Likewise for other common extensions such as word documents. The question becomes, does the removal tool author know what these values were prior to the viral infection? Does the tool even detect these changes? I could easily hide a re-install malware executable in such a route, triggered by say a plugin load into internet explorer, or such like.
Next up is the most difficult to recover from - what if said virus starts trampling all over various files you own? It's entirely possible it could patch parts of windows this way, or your user data and programs, storing copies of itself, which means you'd have to know it did this and search for the damaged files, or else scan all files for the payload. Which gets even harder if it is self modifying. If any of these payloads are triggered, a re-install is a likely behaviour.
The final case is the old rootkit, which could hide the infection from the cleaning program. You can go some way to detecting rootkits if you try hard, but it is significantly non-trivial.
I should also point out at this stage that websites offering to clean/disinfect your computer are a great attack vector for any malware author. Emails introducing yourself as Mr So and So with £850,000 USD they just happen to want to give away are pretty obviously frauds to most people, but the computer says "alert, you have a virus" in a way that looks legitimate to your average home user and before you know it, they've installed said "product". They don't necessarily have the technical expertise to realise the scam here.
I do not trust said cleaning tools or services unless they come from reputable vendors.
The insurance industry employs the term "write-off" when the cost of repairing or fixing something is greater than the cost of replacing it. In my mind, undoing the damage to an operating system a "good" (as in, highly effective) piece of malware can do is probably not worth the time and effort it takes unless you are (very) determined to learn about the infection and the behaviour of the malware. So I would write off the install in all likeliness.
That said, some malware is fairly simple and does not impact the system as badly as it could. In which case, a removal tool might well be all it takes to clean it. The problem is knowing that it is in fact just a simple piece of malware.
Further update: Based on this.josh's comment - a lot of malware I personally have seen has not been so advanced as to be incredibly difficult to remove. However, a common trend I have seen on infected PCs is for the PC to be infected with multiple pieces of malware, all doing different things. Often, a single initial infection seems often to be built entirely to do this. Tracking all of those pieces down and deducing whether they're part of a whole, or separate entities and what variant they are is a time-consuming process which keeps full time malware analysts employed at varying reputable vendors. I personally therefore have two questions of "malware removal" tools you find:
- Do their authors have the same level of experience in removing malware as the likes of Symantec, McAfee etc?
- Have their authors had the same amount of time to analyse the malware? I know how to use disassembler tools, but I can tell you the process of working out what something does from disassembly is one that takes a lot of time to learn and time to do even if you're an expert. I know because I'm not that great at it.
I have a hard time believing what appear to be "silver bullet" solutions.
Obviously there is a caveat to this - reputable companies offering virus cleaners (which happens sometimes) are likely to work and unlikely to be malicious. It's about making a judgement call as to how much you trust the author of the tool and how sure you are they are who they say they are. I would say, however, that it is known that some malware is capable of disabling reputable anti-malware products (although it isn't common) and that prevention is pretty much always preferable to cure.
Compare it to being burgled, if you've ever had the misfortune to have that happen. Some things are obviously missing, like the TV. However, to give a full list of what is missing and out of place is very hard to do - did they take X, or did you just leave it at someone else's house? Or in the car? Where's Y? The same applies to malware - a full account of the damage done is hard, especially as, just like thieves, each piece of malware is different. Like thieves, malware has some common traits, like targeting autorun methods so that is what makes it obvious there's been an intrusion, but as I say, fully accounting for everything is hard.