Sounds like you have had your Search hijacked. And there is something in your startups which puts back the settings at each boot.
One thing to try would be to Download and install Ad-Aware. Read all the directions carefully. Be sure to make the backup and do a deep scan. Reboot and scan again.
Here's the link:
http://www.lavasoft.nu/
Download the refupdater. Run it to be sure you have the latest ref files.
http://www.lavasoft.nu/software.html#rfu
Install Adaware. Reboot. Run refupdater. Run Adaware.
There is also another Spyware utility. It's called SSD Spybot Search and Destroy.
Here's a link for that. Between the two programs, I hope you will remove whatever this is.
http://www.lurkhere.com/~nicefiles/index.html
If not. Post back. This kind of thing works by hiding a registry file in your startups and executing it. It is called something like sp.dll or sp.reg depending upon which hijacker.
Sometimes changing the settings back to what you want and then removing the registry file and the reference to it in your startups is enough.
You are running Win2000?
Startup Cop is a download which will get you the information you need as to what is in your startups.
Here's a link to that if you need or want it.
http://downloads-zdnet.com.com/3302-...0.html?tag=mta