I've tried simple things like Right-Click>Properties>Start Menu>Customize>uncheck Search>Apply>OK, then repeating the process and re-checking the Search box, but no luck.
I did find that I the NoFind REG_BINARY did not exist in My Computer\HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer. I added it and set it to 00 00 00 00, but it didn't really seem to do anything...I hope that's not the problem....
Anyway, help?