I've seen this before, we had some customers at the ISP I worked for complaining about gohip.com signature ads showing up in their email all of a sudden.
When deleting cookies in IE, make sure to delete them ALL, manually. Ex's description is how to do it. The "delete files" button in Internet options only deletes expired cookies, current ones will still be there.
I'd also recommend running a firewall if you aren't currently running one. Get Zonealarm from
http://www.zonelabs.com It'll tell you if a program wants to send anything out and ask for permission to let it do so, so you can easily identify and eliminate ad bots that way.
Xayd