I think I have found a temporary solution to this problem try this program:
http://downloads.theregister.co.uk/Windows...la_cleaner.html
It cleans the cache, history, ect. for firefox, mozilla, and thunderbird.
Any progress on cleaning the firefox search history?
I just installed the latest and greatest, but it's still not in there.
:-(