IMAP does support server-side full-text search of bodies. (In mutt, this is invoked with the =b operator of the l command.) Amusingly enough, this works well with real mail servers like dovecot, but it seems to sometimes miss matches with gmail, because gmail's indexes aren't very good.
I've done the same thing for decades with the -v -R options to GNU tar, which cause it to print the block number of each file to stderr while creating the archive. With knowledge of the block number, you can then pipe dd to tar to extract a single file without a linear search. Or, in the case of tapes, you can use mt to seek to the block before you run tar. Of course, something like tarindexer is more convenient!
The speed of accessing a zip -0 archive would seem to be an implementation issue, not a format issue. Why didn't you fix the performance of your zip implementation instead of inventing yet another file format?