No Lens,
Are you still there? I have not seen a response in some time. If you are still around, let us know how things are going now with this issue.
Unfortunately, your post has turned into a dumping ground for everyone that has problems with Search. I strongly suspect that customers experiencing this issue have corrupt projects, which can occur by simply updating a complex project file from one version to the next. For that, I'm sorry if this happened to you.
For all experiencing this issue, please test with a brand new project and report back with the results. If the results are that search works with a new project but has problems on a project you updated, your project is likely corrupt.
The iron clad way to avoid corrupt projects is by remaining on the same version of Premiere Pro throughout the life of your project.
If you are experiencing this issue with a brand new project, look at the media you are using. If it comes from a camcorder that stores files in folders a compact flash disk, you need to copy all those folders, the entire contents of that CF card, to your hard drive. Then, import the footage via the Media Browser and not File > Import. If you ingested the media without any metadata, Premiere Pro might have a hard time finding specific clips based on that metadata - so that can also cause your search field to not function correctly. Please check that, as well.
Thanks,
Kevin