When you start Safari again, the search history should be empty.
Somebody could probably build a shell script that searches the History.plist XML file and deletes the <dict> sections AND resets the Safari plist at the same time. I'm not that good with string manipulation, so I'm hoping somebody with experience could pick this up. Then that shell script could be made into an AppleScript or set up with Automator. Wishful thinking?
Extended Keyboard Server, Mac OS X (10.5.6), Sure, blame the computer with ONE BUTTON!