Perhaps they meant seekable when compressed? As in the header for each object has the compressed length of object? Presumably in a meta data header with name, compression format, claimed uncompressed length, date, etc.
Personally I'd like a tool that lets me extract files from TB size archives easily without decompressing everything. Only virtual disk images seem to have that random access functionality. There are ways of using gzip/bzip/xz that use sync points, so you could produce a compatible archive that allowed decompressing metadata bits, though it would suck for many small files.
Tar is not streamable when compressed with gzip. 4Q supports compression on a per-file basis and thus can support streaming and compression at the same time. Zip also supports compression on a per-file basis, but it requires an index and thus is not streamable.
You can stream zips if you don't use compression, and you can use compression on files small enough to hold in memory. I work at Barracuda Networks, and we actually do this every day.[1]
