The easiest way to clear the Start / Search / For Files or Folders history is to run the following .reg file:

REGEDIT4

\[-HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\Explorer Bars\\{C4EE31F3-4768-11D2-BE5C-00A0C9A83DA1\}\FilesNamedMRU\]
If you wish to clear the Containing text history also:
REGEDIT4

\[-HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\Explorer Bars\\{C4EE31F3-4768-11D2-BE5C-00A0C9A83DA1\}\ContainingTextMRU\]

\[-HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\Explorer Bars\\{C4EE31F3-4768-11D2-BE5C-00A0C9A83DA1\}\FilesNamedMRU\]
You could run a logoff script:

regedit /s <path>\filename.reg