Related: For fast filesystem search on Windows (NTFS) I cannot recommend enough Everything [0]. Instant search through all drives. This app really shines. Under 1 Mb install size, blazing fast interface (can be bound to global hotkey), command line interface, optional HTTP interface, small memory footprint (depends on the size of indices). Really, if you haven't seen it, check it out.
It basically connects to the NTFS database, fo that's why it is instant. Still don't understand why OS does not do this.