I also discovered this project which aims to do the obvious, that is to combine the fast MFT read with the USN journal. http://mftscanner.codeplex.com/
So when everything works as planned, you should only need to do the 5-10 second MFT scan once after booting, and further use will access the cached name records and the change journal.
By my understanding this approach allows practically instant file search completely without indexing and background stuff running. The only question is, why none of this is provided to explorer users!