In Start Search type regedit and hit the enter key:
Browse the following path:
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\WordWheelQuery
Select the DWORD keys storing the search history value.
Right-click the selection and choose the Delete option.
Click the OK.