I'd suggest doing a "Disk Cleanup". That will erase all of the offline IE content and temp folders (where spyware/malware likes to hide). Also run a spyware detection program like spybot to clean out any pests.
You never mentioned what version of windows you're running, and what service pack level. Also, switch to a non-IE browser like Firefox or Opera. You'll have much less problems with malware and Internet related pests.
Check out this article for more info,
http://blogs.zdnet.com/Spyware/index.php?p=733