Here's the thing: Malware in recent years has become both sneakier and nastier:
Sneakier, because it travels in packs. Subtle malware can hide behind more obvious infections. There are lots of good tools listed in answers here that can find 99% of malware, but there's always that 1% they can't find yet. Mostly, that 1% is stuff that is new: the malware tools can't find it because it just came out and is using some new exploit or technique to hide itself that the tools don't know about yet. The anti-malware tools still have their place, but I'll get to that later.
Malware also has a short shelf-life. If you're infected, something from that new 1% is very likely to be one part of your infection. It won't be the whole infection: just a part of it. Security tools will help you find and remove the more obvious and well-known malware, and most likely remove all of the visible symptoms (because you can keep digging until you get that far), but they can leave little pieces behind, like a keylogger or rootkit.
Nastier, in that it won't just show ads, install a toolbar, or use your computer as a zombie anymore. Modern malware is likely to go right for the banking or credit card information. The people building this stuff are motivated by profit, and if they can't steal from you directly, they'll look for something they can turn around and sell. This might be processing or network resources in your computer, but it might also be your social security number.
Put these two factors together, and it's no longer worthwhile to even attempt to remove malware from an installed operating system. I used to be very good at removing this stuff, to the point where I made a significant part of my living that way, and I no longer even make the attempt. I'm not saying it can't be done, but I am saying that the cost/benefit and risk analysis results have changed: it's just not worth it anymore. There's too much at stake, and it's too easy to get results that only seem to be effective.
Lots of people will disagree with me on this, but I challenge they are not weighing consequences of failure strongly enough. Are you willing to wager your life savings, your good credit, even your identity, that you're better at this than crooks who make millions doing it every day? If you try to remove malware and then keep running the old system, that's exactly what you're doing.
I know there are people out there reading this thinking, "Hey, I've removed several infections from various machines and nothing bad ever happened." I suggest you need to add "yet" to the end of that statement. You might be 99% effective, but you only have to be wrong one time, and the consequences of failure are much higher than they once were. You might even have a machine already out there that still has a ticking time bomb inside, just waiting to be activated or to collect the right information before reporting it back. Even if you have a 100% effective process now, this stuff changes all the time. Remember: you have to be perfect every time; the bad guys only have to get lucky once.
In summary, it's unfortunate, but if you have a confirmed malware infection, a complete re-pave of the computer should be the first place you turn instead of the last.
Here's how to accomplish that:
Before you're infected, make sure you have a way to re-install any purchased software, including the operating system, that does not depend on anything stored on your internal hard disk. For this purpose, that normally just means hanging onto cd/dvds or product keys1, but the operating system may require you to create recovery disks yourself. Don't rely on a recovery partition for this. If you wait until after an infection to ensure you have what you need to re-install, you may find yourself paying for the same software again.
If you suspect you have malware, look to other answers here. There are a lot of good tools suggested. My only issue is the best way to use them: I only rely on them for the detection. Install and run the tool, but as soon as it finds evidence of a real infection (more than just "tracking cookies") just stop the scan: the tool has done its job and confirmed your infection.
Now, at the time of a confirmed infection, take the following steps:
- Check your credit and bank accounts. By the time you find out about the infection, real damage may have already been done. Take any steps necessary to secure your cards, bank account, and identity. Change passwords at any web site you accessed from the compromised computer. Do not use the compromised computer to do any of this.
- Take a backup of your data (even better if you already have one).
- Re-install the operating system using disks shipped with the computer, purchased separately, or the recovery disk you should have created when the computer was new. Make sure the re-install includes a complete re-format of your disk.
- Re-install your applications.
- Make sure your operating system and software is fully patched and up to date.
- Run a complete anti-virus scan to clean the backup from step two.
- Restore the backup.
If done properly, this is likely to take between two and six real hours of your time, spread out over two to three days (or even longer) while you wait for things like apps to install, windows updates to download, or large backup files to transfer... but it's better than finding out later that crooks drained your bank account. Unfortunately, this is something you should do yourself, or a have a techy friend do for you. At a typical consulting rate of around $100/hr, it can be cheaper to buy a new machine than pay a shop to do this. If you have a friend do it for you, do something nice to show your appreciation. Even geeks who love helping you set up new things or fix broken hardware often hate the tedium of clean-up work. It's also best if you take your own backup... your friends aren't going to know where you put what files, or which ones are really important to you. You're in a better position to take a good backup than they are.
Soon even all of this may not be enough, as there is now malware capable of infecting firmware. Even replacing the hard drive may not remove the infection, and buying a new computer will be the only option. Thankfully, at the time I'm writing this we're not to that point yet, but it's definitely on the horizon and approaching fast.
If you absolutely insist, beyond all reason, that you really want to clean your existing install rather than start over, then for the love of God make sure that whatever method you use involves one of the following two procedures:
- Remove the hard drive and connect it as a guest disk in a different (clean!) computer to run the scan.
- Boot from a CD/USB key with its own set of tools running its own kernel. Make sure the image for was obtained and burned on a clean computer. If necessary, have a friend make the disk for you.
Under no circumstances should you try to clean an infected operating system using software running as a guest process of the compromised operating system. That's just plain dumb.
Of course, the best way to fix an infection is to avoid it in the first place, and there are some things you can do to help with that:
- Keep your system patched. Make sure you promptly install Windows Updates, Adobe Updates, Java Updates, Apple Updates, etc. This is far more important even than anti-virus software, and for the most part it's not that hard, as long as you keep current. Most of those companies have informally settled on all releasing new patches on the same day each month, so if you keep current it doesn't interrupt you that often.
- Do not run as administrator by default. In recent versions of Windows, that is as simple as leaving the UAC feature turned on.
- Use a good firewall tool. These days the default firewall in Windows is actually good enough. You may want to supplement this layer with something like WinPatrol that helps stop malicious activity on the front end. Windows Defender works in this capacity to some extent as well.
- Run current anti-virus software. This is a distant fourth to the first three, as traditional A/V software often just isn't that effective anymore. It's also important to emphasize the "current". You could have the best antivirus software in the world, but if it's not up to date, you may just as well uninstall it. For this reason, I currently recommend Microsoft Security Essentials. (Since Windows 8, Microsoft Security Essentials is part of Windows Defender.) There are likely far better scanning engines out there, but Security Essentials will keep itself up to date, without ever risking an expired registration. AVG and Avast also work well in this way. I just can't recommend any anti-virus software you have to actually pay for, because it's just far too common that a paid subscription lapses and you end up with out-of-date definitions. It's also worth noting here that Mac users should also run antivirus software. The days when they could get away without it are long gone.
- Avoid torrent sites, warez, pirated software, and pirated movies/videos. This stuff is often injected with malware by the person who cracked or posted it — not always, but often enough to avoid the whole mess. It's part of why a cracker would do this: often they will get a cut of any profits.
- Use your head when browsing the web. You are the weakest link in the security chain. If something sounds too good to be true, it probably is. The most obvious download button is rarely the one you want to use any more when downloading new software, so make sure to read and understand everything on the web page before you click that link.
Also, prefer to download the software and updates/upgrades directly from vendor or developer rather than third party file hosting websites.
1 You should also backup your data, but that's really a separate issue: if your system security was compromised, your backups are likely compromised, too.