Weird that the MS website isn't working for you - works fine for me. Maybe try googling "Microsoft Malicious Software Removal Tool"? It's unheard of for me to recommend an MS tool, so you know it's worth it
As far as the registry goes, most viruses (virii?) put an entry in "Run" or "Run Once" (sometimes both). Usually, all this does is restore the offending .exe when you think you've deleted it. I can't remember the exact path to these entries, but definitely worth a search in your registry editor.
Do you have any filenames associated with the trojan/virus/malware/whatever? You can often google those to find more specific details on removing a particular offender. A lot of security sites post individual tools specifically designed to remove particular problems, so a search might take you to something like that.