A couple other things to try if you can't find the process that's serving up the ads...
In Internet Explorer, go to TOOLS | INTERNET OPTIONS. Then click SETTINGS and then VIEW OBJECTS. The window that comes up shows all the plugins that piggyback on IE (like Flash, Java, Quicktime, ... Gator...). I don't recommend taking out anything you don't recognize unless you know what you're doing, but certainly if you see something like Gator, remove it.
If you really know what you're doing, you can also go to the command line and type netstat -a. This command lists all the ports that your computer connected to. Those ads have to be served up from somewhere, so your computer has to be listening for incoming ads on some port or connecting to a site to pull the ads. Hopefully it's some bizzare port number--if so, just type it into google (like search for "port 22325") and chances are somebody else has posted solutions for getting rid of whatever program is doing it.
Last, take a screenshot of your desktop when one of the ads pops up, paste it into mspaint or Photoshop, save it as a .JPG, and then upload it to some web space. Link to it in the "Out of the Blue" topic here and maybe we can figure out what's causing it then. It's something that you installed, either knowingly or by mistake--it's not some sort of Windows XP vunerability (I say with 99% confidence).