NSMetadataQuery won't find files in Lion, Mountain Lion, or Mavericks

If you create a vanilla project and make this the implementation of your app delegate:

@interface TESTAppDelegate ()
@property (nonatomic, strong) NSMetadataQuery *query;
@end

@implementation TESTAppDelegate

- (void)applicationDidFinishLaunching:(NSNotification *)aNotification
{
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(searchProgressed:) name:NSMetadataQueryGatheringProgressNotification object:nil];

    NSMutableArray *predicates = [@[] mutableCopy];
    #define add(format, ...) { \
        [predicates addObject:[NSPredicate predicateWithFormat:format, ##__VA_ARGS__]]; \
    }

    //Toggle which of these lines are commented to experiment with breaking the query
    //add(@"kMDItemKind like[c] %@", @"*"); //Works
    //add(@"(kMDItemContentType != 'com.apple.mail.emlx.part')"); //Works
    //add(@"(kMDItemContentType == 'public.data')"); //Works
    //add(@"kMDItemFSName like[c] %@", @"*"); //DOES NOT WORK
    add(@"kMDItemFSName like[c] %@", @"*Nashville*"); //works...

    self.query = [[NSMetadataQuery alloc] init];
    [_query setPredicate:predicates.count > 1? [NSCompoundPredicate andPredicateWithSubpredicates:predicates] : predicates.lastObject];
    [_query setSearchScopes:@[[@"~/Downloads" stringByExpandingTildeInPath]]];
    NSLog(@"Query %@", [_query startQuery]? @"started" : @"could NOT start!");
}

- (void)searchProgressed:(NSNotification *)note
{
    NSLog(@"searchProgressed: %li", _query.resultCount);
}

@end

You should be able to confirm this following highly abnormal behavior "recently" introduced (post-Lion) on NSMetadataQuery: it apparently no longer works.

If you run the app as-is, it should log something like "searchProgressed 1204", meaning the query found results. But, if you run it after commenting out the other predicate, it finds nothing.

I have tried many variations of that line, including various formulations of the wildcard, or the %K placeholder, changing the LIKE[c] placeholder to other forms, and, of course, using things like NSMetadataItemFSNameKey, NSMetadataItemURLKey, and kMDItemContentType. Nothing works except the single, simplest case above.

I must be missing something huge about NSMetadataQuery, which I used extensively with great success before, because otherwise everyone would be commenting on how useless it is.

I’m just guessing, hopefully this doesn’t violate StackOverflow’s rules:

I wonder if Apple doesn’t want Spotlight used to list the contents of directories completely—it’s probably a pretty inefficient way to do that—so they’re filtering out “overly-broad” queries. If you change the “” to something else, like “F”, does it work?

‘-startQuery' returns a BOOL, have you seen what it’s returning?