Since there is spyware that can cause that you should first rule it out.
Download/run HijackThis from:
http://majorgeeks.com/downloads31.html

Do not remove anything with it until you get advice on what to remove, HJThis will
list many apps that are needed along with the bad ones. Removing items listed
hap-hazardly without knowing what they are can/will create a royal mess. Read the
quick start here on how to create a log file that can be copied/pasted into a forum
that can provide assistance on removal of unwanted pests.
http://mjc1.com/mirror/hjt/#quick

Then post the logs to an appropriate NG here where they specialize in
spyware/hijacker removal:
http://forums.spywareinfo.com/

http://forum.aumha.org/

Many people have gotten relief for this kind of problem by following the fix
described in this article:

Recovering From a Failed Internet Explorer Upgrade in Windows 98
http://support.microsoft.com/default.aspx?scid=kb;en-us;249191