Well, it's very-very fast in 8.1. I don't know why it does not find the document you want - it works quite well for me, YMMV obviously.

Have you used Everything?

It is instant file name search. I guess recent Windows could have improved file name searching, but it has classically been pretty bad.

Actually not really if you set up an index on C:\ it is quite fast, which is basically the main difference. But there is not one by default so you need to add it.

"will not find whatever document you want 90% of the time"

Absolute rubbish.

Apparently different people have different experiences. For me, it doesn't work about two thirds of the time.