Go to Start > Run, type in "regedit" (without the quotes), click OK. When the registry editor opens, navige using the little + signs, to:
HKEY_CURRENT_USER\Software\Microsoft\Windows\Current Version\Explorer\Doc Find Spec MRU. Click on that "Doc Find Spec MRU" folder in the left pane and it's contents will appear in the right pane. You will notice that your searches are prefixed with a letter, delete all those prefixed with a letter or whichever particular searches you want to delete. To delete them highlight and choose delete from the keyboard or right click and choose delete from the context menu.
It goes without saying that you should backup the registry before making any changes, jut in case. To back up click on the "Doc Find Spec MRU" folder and go to File > Export, give the reg file an apt name so you'll remember what it is and export to the Desktop. If anything goes wrong you can double click that reg file to restore the registry to how it was before you edited it.