ZIP with LZMA compression is one possibility. Random seek were always supported, and later versions also gained support for modern encryption, modern compression, and IIRC Unix permissions too.
ZIP with non-deflate compression is just silly. If you are not going to create defacto-standard compatible .zips then you might as well use a better archiving format.
Your choice of tools always depends on the use case. If you're only going to be creating these archives for internal use, or will be exchanging them/reading them on modern Unix-like systems, then there is no worry about the decompressor not supporting LZMA. If you need to exchange files with feature-poor systems, then yes - stick to the de-facto standard.
Besides, what "better" archiving format are you going to use? Tar clearly isn't one (the great... grandparent comment wouldn't be asking for alternatives if it were). "Defacto standard" ZIP files have a poor compression ratio. 7z feels strange to use in a professional setting or for long-term storage. RAR is a closed-source abomination. Are there any other "better" archiving formats that have wider (de)compressor adoption than ZIP+LZMA?
