I've had this problem, it was a nightmare to sort out.
If you've got your windows disk then un-install & re-install Internet Explorer first as it sounds like its messed up part of your regisrty, do this from the actual disk, not just the add/remove programes list, as then it does it fully & doenst leave any bad traces.
Then check for spyware
I use ad-aware, its all free
http://www.lavasoftusa.com/products/ad_aware_free.php
Avast antivirus is very good imo, its all free aswell (you have to register after a set date, but even this is free)
Once its all up & running you dont have to touch it again, updates itself, scans itself - its great if you are absent minded / lazy such as myself :p
I had lots of background problems with firefox, it clashed with a huge part of my registry & caused me lots of updating problems & i couldnt view any flash videos.
I have it on both the pc & the laptop on vista with no problems (i probably shouldnt have said that lol, guarantee the pc will crash / something)
http://www.avast.com/