I dumped the original windows search when I found about
locate for windows . It's a very good alternative to the bad search of windows. It should be a good starting point. And it's free!
If you decide to try, be sure to get the latest "daily" release. It is very stable and include a lot of fix. If I remember correctly, you need to install the latest official release (2.99.5.10100) and then unzip the daily release (2.99.6.3190) in the installation folder.
You can configure which disk to scan, when to scan and such. Like locate for *nix, the search is based on a database, so recent changes to the file system are not immediatly searchable, but result (at least for file search) is almost instantaneous. You can update manually if you need to.