Cannot find server or DNS Error

I am not sure if this should be here of over in networking but at this point I am at wits end...

Monday I was out looking around for free borders to use on a website I'm working on and (if I could get my hands around a responsible party's neck)... I got hit with some sort of hijacking/spyware something or other. In the process of trying to remove this stuff I've down loaded and run I don't know how many things (it's interesting how the free stuff seems to find more than the thing I forked out $39.95 for but I digress). I've run Ad-ware and Spybot Search & Destroy. Now I am in the happy situation of IE can not download anything.

Dial-up connection
Windows 2000 5.00.2145 service pack 4
IE 6.0.2800.1106

The basic situation: I try browsing to any site and I get the glorious "Cannot find server or DNS Error." I go into Outlook Express and it falls flat on its face... At the DOS prompt I try to ping anything (www.google.com for example) and it says "unknow host www.google.com." I run nslookup on www.google.com and I can ping any of the dotted addresses. I put the dotted address in IE and it pulls up the page (Google in this case and I'm starting to think I'm onto something). I go into Outlook Express and plug in the numbers for the mail servers and it starts working. At the moment I'm connected to MajorGeeks using http://66.98.158.200/forumdisplay.php?s=&daysprune=&f=21. I'm also seeing services.exe, rundll32.exe and svchost.exe at random just start using all avaliable CPU ... Did Spybot or Ad-aware or running Hijack This clobber something or have I deleted/cleared something involving DNS (dumb question as that would seem to be the case)? I've mathed the settings on the desktop (has the problems) against a laptop and I don't see anything being different. Looking around (as best as I can at the moment) I found one article that basicaly said, "rip out dial-up networking and TCP/IP and reinstall them" and I'm thinking (1) do I really want to do that, (2) is that what it's going to take???

If somebody can provide some pointers - God I would be mighty grateful.