even today local search is hopelessly broken

I use FileLocator Pro on Windows, and a fairly organized hierarchical structure for all my files (that lives outside of the My Documents crap).

It doesn't need indexing - it makes use of very performant MFT querying to speed things up (and can of course search contents as well). Not quite instant unfortunately, but on modern hardware it's not too bad. I tried Everything and other index-based technologies but was never quite satisfied. I do really miss LookOut for email, that's one of the best search experiences I ever knew.