I've had clients who were so badly compromised, that they had a re-flashed malicious bios, PCI card, and firmware on the hard drive! Fortunately they didn't really have anything worth stealing, so I re-flashed all the firmware, and ran a diagnostic repair on the hard drive using the OEM tools. This after replacing the firmware with the newest version of course. Low level formatting no longer works(in the traditional sense) on modern hard drives, but the diagnostic un-hides any sectors marked as damaged where malware re-installation packages can be hiding. Then I do something like the gutmann wipe, but for modern hard drives, i.e. Darik's Boot and Nuke.
If you do a thorough job scanning the hard drive with Malewarebytes Anti-malware Anti-Rootkit in normal mode, you can usually breath a sigh of relief - but if you have anything to lose, that isn't good enough. Always assume you are compromised and use kernel level solutions like a good HIPs - Comodo Defense +, Trusteer's Rapport, and Avast - where the kernel level characteristics of these solutions resist tampering by any left over malware. Also a good password manager can be golden, where encryption is used; this should also be rated as a good kernel level tool. Of course these solutions have to be already on the computer before the compromise, or you cannot trust the installation process will be successful!
After a wipe and reinstall, I still do a PE scan of the hard drive using DVD rescue disks by several solutions, like Kaspersky's Rescue 10 and Avast, and then just for good measure an MBAM safe mode scan with MBAR as previously mentioned.
Even if you don't have anything to lose, it can still pay to do that same scan without a wipe an reinstall. invariably I've found more rootkits, backdoors, or other APTs(Advanced Persistent Threats). It is a good idea to wait 24 hours before doing this, and keep the unit offline, before and during scanning, so any zero day threats have a chance of being found. Also it prevents the malware from calling their minions to change the characteristics of the malware in preventing detection.
The really good question is how much can you lose, and is it really worth the time, effort, and money to go deep in rooting out infection. Most of the time, a cursory cleaning is good enough for folks that have nothing to lose, and don't bank, shop, or otherwise expose personal information online.
Don't give up on Skype, just make sure you have both a good hardware AND software firewall, and don't allow Skype to start when the computer does - it is not a bad idea to shut Skype down after using it!