How does one get rid of such a thing, short of reinstalling the OS, given that I was left in a situation where I couldn't boot the computer?

Is the fix to boot from a CD and then manually yank out the malware, or is there something more elegant? I'm religious about making rescue disks for laptops, but I hadn't thought I'd needed one for my desktop machine.

If I get caught again (not that I have any intention of doing so), I'd like to know how to deal with it myself. And how to fix it for someone else, for that matter. Don't want to pay for this more than once.