I'm a big fan of Everything (and recently donated to the developer). I tried this Google app and was pleased to see that it seems just as fast as Everything for local file search. Presumably they use the same underlying mechanism for searching files (something about hooking into the NTFS index). I might give it a shot.

(disclaimer: I work at Google, but nothing related to this app)