O Tar realmente é o melhor formato para arquivos. Todo sistema que você deseja recuperar terá isso.
Eu uso o módulo Python do tarfile para fazer meus arquivos tar.gz e um arquivo de índice com hashes. Eu tenho meu programa criar um novo tarball quando o atual atinge um determinado tamanho. Você poderia então executar o mkisofs e o cdrecord com o popen para criar os ISOs e gravá-los no disco.
Eu uso tarsum.py para verificar os hashes durante a recuperação.