I finally found a solution for my nephews malware issue. Maybe this could help you guys too.
1st the problem we were having with the malware, was with the redirection with the google,msn and yahoo search engines. Every search was redirected from "go.google"
2ndly we were having the same problem as TLarry in his 1st post.
Until I went to this site "www.freedrweb.com/cureit/" and DLed the free program and did a full scan. Which the scan detected and deleted
"c:\windows\system32\drivers\tdsswagp.sys
infected with BackDoor.Tdss.29 "
And now I dont have any issues with this stupid malware anymore.