My method...
First things first, disconnect the machine from the network. Any and all tools either go on a CD, or on a blank usb key that will be formatted after use.
On windows, would have been to check out the Services for anything not signed by Microsoft Corporation and seeing if anything there looked suspect amongst the various services and drivers that are loaded there, especially if there is somthing with the same name as somthing officially Microsoft.
From there, System internal's Process Explorer is a great tool, and can not only show you the process names, but also their paths. Nothing looks like svchost.exe like another svchost.exe, but when you see that one of them is being run from somwhere that is not windows\system32 , you have probably found your culprit.
A quick look at the registry run and runonce keys can turn up the usual suspects, but as there are so many startup points, a tool like autoruns (systeminternals again) can list a lot of this.
Kill any strange processes you may see in process explorer, stop anything wierd in the services, stop from starting anything that seems nasty from the registry. You could also run somthing like cureit that is supposed to be an efficient standalone scanner that runs on a live system. It's free too, so it's worth a shot and let it do it's magic. See if it finds anything, and clean it. You may not have to go any further.
While this is running, from a known clean system, download a live CD / Live usb antivirus solution, burn to a CD or copy this to another USB key (do not reuse the one used to load cureit & systeminternal's tools as it's potentially tainted now). If your are not happy with your live system check, then shut down the computer, then restart and boot on the CD/Key and let that antivirus go over the "dead" system - At the very least it will be able to clean a bootsector virus... and after that, using the live CD before rebooting, you can backup any wanted files from My Documents, your address book, your email app's data files and files on the desktop to an external drive. Disconnect the drive, and reboot...
If this solved your problem, you are golden. If it did not, then you have the reinstall route - just run the files you backed up after the liveCD AV scan through an antivirus on your clean system. You should have most if not all of your most recent data to hand, you now just have to spend a day on reinstalling windows, installing the updates & patches, reinstalling your tools & apps, patching them, then restoring your data. At worse, it would be a full weekend job...