Windows search has been broken for a _long_ time. Agent Ransack¹ is one of the first things I add to a fresh Windows install. Soon after some unix-a-like ports go on too (usually via cygwin) so I can use find, grep, and friends. For filename based search on NTFS volumes, WizFile² is useful too as it scans the MTF instead of navigating the directory structure bit-by-bit which can be significantly faster no matter how modern your local drives are.
This is the main reason I don't bother even trying Bing – if they can screw up local file search this much, how useful can their global search really be?
--