Start gconf-editor:
gconf-editor
Go to /apps/gnome-settings/gedit/history-gedit2_search_for_entry and /apps/gnome-settings/gedit/history-gedit2_replace_entry_with and remove the content there:
How can I clear gedit text search / replace history?