Start-->run-->regedit-->locate the following path:
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer\NoFind
If NoFind has the value 01 00 00 00 change it to 00 00 00 00
Exit the registry and restart. See if that fixes the search function.