To remove all search history requires a registry edit. This is a dangerous thing to do if you don't know what you are doing.
Click Start->Type regedit in the search box and hit enter.
Navigate to the registry entry: HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\WordWheelQuery
Delete the WordWheelQuery Folder.
Alternatively if you just want to delete a few entries you can open the pre-typed text as pictured and just highlight the entry you want to delete and hit the DEL key.
The image shown is from Win2k8 r2 but it should be the same on Win7.