That sounds strange but have you tried deleting you temporary internet files?
Also, are you using IE? If so don't. Nah actually, check to see if anything has been added to the links toolbar and also check control panel for any "search bars" they are added so easily these days.
