The history is kept at the following registry key:
HKEY_CURRENT_USER \ Software \ Microsoft \ Windows \ CurrentVersion \ Explorer \ WordWheelQuery
I have found no GUI way to disable search history, but you should have luck if you right click on the registry folder and change the permission to "everyone" and deny all, then, Windows will fail to write/remember your search history.
I have tested this inside of a Virtual Machine and whilst I can't see the future (I wish!), I cannot see any application / security logs coming up - it seems a perfect way of doing this as it simply blocks the system from writing any changes. What you can even do is just give read permission and deny write/Full control, then you can pre populate the search with just a few options.