OK, so I had a hunch that I had some infections on my machine. I booted into safe mode and ran some deep scans with Zonealarm. It found nothing. I ran a few scans using some portable virus scanners, like EmsisoftEmergencyKit that found some trojans! I quarantined these items and had them deleted. These seem to have been in legacy files that probably existed prior to my current OS installation so maybe they were not "active".

Question: what is the best way to find (and correct) infections on your PC?

Should I login with safe mode *without* networking to an alternate Windows user (not the one I believe was used to get the infection) and run a deep scan? Use a few complimentary malware/virus/spyware/rootkit scanners? Suggestions?