This may work, but your search history will continue to be logged until you do this (assuming you use IE):
Goto Tools>Internet Options in IE
Click on the tab for content.
Under the section for "Personal Identification", there is a button for AutoComplete. Click this button.
Uncheck the box next to Web addresses, Forms, User names and passwords on forms, and then click the OK button.