I quote:

The deepcat example (deepcat:"musicals") seems to be off. For some reason, if the category's first letter is not capitalized, the search doesn't seem to search in the subcategories. First see Category:Musicals and then compare these searches: deepcat:"musicals" vs.deepcat:"Musicals". The latter search also gives the following warning: "''A warning has occurred while searching: Deep category query returned too many categories''". Maybe we should change the example search and category to a smaller category with correct capitalization, for example to deepcat:"Musicals by topic"?

I think this indeed a bit weird and possibly should automatically take into account Manual:$wgCapitalLinks and Manual:$wgCapitalLinkOverrides