You have successfully located the problem, and it seems to be an Adobe bug. When InDesign created fixed-format EPUB files from a Book containing multiple files, it fails to make it searchable. I will report this to Adobe in the proper forum.
I won't say this is wrong, but I'll make two observations: the fixed-page format is limited and problematic in many ways, and should only be used for very selective projects (primarily "art" books where the page images are more significant than the text). Many aspects of EPUB are less reliable and less 'functional' with FXL export. This could be another.
I am, however, having trouble figuring out where the bug would come in, as the EPUB export creates absolutely nothing to do with searching (no index, no keyword file, etc.) The search function is entirely based on the reader, which searches the XHTML content files for matches. Unless something has changed, you noted that searches worked on the vanilla/standards-based readers, but not on two nonstandard readers (ADE, which simply should not be used by anyone for anything, and the Apple reader, which has a lengthy set of quirks to suit Apple's preferences). That does not point to an integral ID flaw.
I'll also note I've never before seen the problem reported. It seems if there was a systemic flaw here, someone else would have run into it before now.
I'll have to experiment (and first, I'll have to find some material to export to FXL, which I never use), but I'd say the odds are that the bug has little to do with ID's export. ID does have its quirks and limitations, but again, there's no technical basis for an otherwise valid EPUB to be un-searchable.
You might run your examples through a validator like EPUBcheck and see if the two variations show any significant technical differences. (I don't think much of validators for exported EPUBs, but in rare instances they can spot structural glitches.)