On a Windows system, you can use regedit (Click on Start - Run, then type regedit and click OK). Once Registry Editor is up, you can use the Edit - Find menu command and search for instances of "MRUList", which stands for Most Recently Used List.
Eventually, you'll find the one for file search history. You can then right-click and delete the keys which are related to the file names you searched for and want to remove. Then, right-click and modify the MRUList key such that its value is empty.
As always, backup the registry to a floppy before you do anything (use the Export Registry File menu command).
An easier way to do this is to install and use TweakUI, which I know is available on a full (not an upgrade) version of a Win9x CD. You'll have to search for the appropriate file on CD, right-click on it, and choose Install. This will install TweakUI as a Control Panel extension. Open the TweakUI tool and find a tab labeled Paranoia, which has settings to clear all MRULists upon exiting Windows.
I haven't done that for some months now and being at work, I can't take the time to elaborate further. If you need further instruction regarding the latter, perhaps I can answer back this evening, or another individual can post as well.
Good luck!