It could reside anywhere if the program which planted it was ran under an administrative account and granted permissions. Typically you will also find malware in temp folders (e.g. IE cache), as some are guaranteed to be writeable by default, even for standard users -- a perfect breeding ground for malware.
The most effective second stage malware or the ones that cause the most symptoms are rootkits - kernel-mode drivers so they're usually hidden in "c:\windows\system32\drivers" or infect the MBR. Use Autoruns to identify them. Often their initial payloads are deployed to temporary internet files or a hidden user directories. Knowing these directories usually doesn't even matter once the system is infected because they controlled by the rootkit and even if you did manage to delete them they would be quickly rewritten elsewhere. I've yet to find effective anti-virus software for removal so a combo platter, starting with a solid Cleanup or Cleaner; run Combofix from the admin profile in in Safe Mode (run as Administrator) and then sysinternals tools to nitpick out any stragglers
Malware could be anywhere. From personal experience, I've usually found them in the Program Files folder. If it's a huge worry, you might want to run a scan once every few days. I highly recommend Microsoft Security Essentials: http://www.microsoft.com/security_essentials/