> It was a simple linear search through files which could take a while on larger folders, but was reliable and predictable since it did not rely on a background indexing service which seems to get stale or just plain wrong most of the time.

It would be easy to have your cake and eat it too. Have the file search default to the index. Allow frustrated users to then click a button that says "search harder" which would initiate the full enumeration of the relevant filesystems. Of course some UX professional will tell me I'm wrong, they don't like anything they didn't think of themselves.