Head over to Trendmicro and do an on-line scan. They'll check for viruses and malware... and may give you different results than you've experienced before.
And, to echo wisdom from TDC, it's usually a wise move to disable the system restore and clean everything up from safe mode... before it has a chance to load. Just be sure to re-enable the system restore afterwards...
You also didn't mention HiJack This. I'd grab the latest copy and run it... it's different from the other malware-eliminators in that instead of looking for known bad things and correcting them, it highlights known potentially bad behaviors (like registry settings) and lets you fix them. Careful, though... it's a potent tool. Research everything before you decide to blow it away.