У меня были проблемы с распаковкой файлов tar и zip которые я получаю от пользователей Windows. Хотя я не отвечаю на вопрос «как создать архив, который будет работать», приведенные ниже сценарии помогают правильно распаковать файлы tar и zip независимо от оригинальной ОС. 
ВНИМАНИЕ: необходимо настроить кодировку источника вручную (cp1251 , cp866 в примерах ниже). Параметры командной строки могут стать хорошим решением в будущем.
Деготь:
#!/usr/bin/env python
import tarfile
import codecs
import sys
def recover(name):
    return codecs.decode(name, 'cp1251')
for tar_filename in sys.argv[1:]:
    tar = tarfile.open(name=tar_filename, mode='r', bufsize=16*1024)
    updated = []
    for m in tar.getmembers():
        m.name = recover(m.name)
        updated.append(m)
    tar.extractall(members=updated)
    tar.close()
Почтовый индекс:
#!/usr/bin/env python
import zipfile
import os
import codecs
import sys
def recover(name):
    return codecs.decode(name, 'cp866')
for filename in sys.argv[1:]:
    archive = zipfile.ZipFile(filename, 'r')
    infolist = archive.infolist()
    for i in infolist:
        f = recover(i.filename)
        print f
        if f.endswith("/"):
            os.makedirs(os.path.dirname(f))
        else:
            open(f, 'w').write(archive.read(i))
    archive.close()
UPD 2018-01-02: Я использую пакет chardet , чтобы угадать правильную кодировку необработанного фрагмента данных. Теперь скрипт работает из коробки на всех моих плохих архивах, а также на хороших. 
Что следует отметить:
- Все имена файлов извлекаются и объединяются в единую строку, чтобы сделать больший фрагмент текста для механизма кодирования. Это означает, что несколько имен файлов, закрученных по-разному, могут испортить предположение.
 
- Специальный быстрый путь был использован для обработки хорошего текста Unicode (
chardet не работает с обычным объектом Unicode). 
- Тесты добавляются для тестирования и демонстрации того, что нормализатор распознает любую кодировку на достаточно коротких строках.
 
Окончательный вариант:
#!/usr/bin/env python2
# coding=utf-8
import zipfile
import os
import codecs
import sys
import chardet
def make_encoding_normalizer(txt):
    u'''
    Takes raw data and returns function to normalize encoding of the data.
        * `txt` is either unicode or raw bytes;
        * `chardet` library is used to guess the correct encoding.
    >>> n_unicode = make_encoding_normalizer(u"Привет!")
    >>> print n_unicode(u"День добрый")
    День добрый
    >>> n_cp1251 = make_encoding_normalizer(u"Привет!".encode('cp1251'))
    >>> print n_cp1251(u"День добрый".encode('cp1251'))
    День добрый
    >>> type(n_cp1251(u"День добрый".encode('cp1251')))
    <type 'unicode'>
    '''
    if isinstance(txt, unicode):
        return lambda text: text
    enc = chardet.detect(txt)['encoding']
    return lambda file_name: codecs.decode(file_name, enc)
for filename in sys.argv[1:]:
    archive = zipfile.ZipFile(filename, 'r')
    infolist = archive.infolist()
    probe_txt = "\n".join(i.filename for i in infolist)
    normalizer = make_encoding_normalizer(probe_txt)
    for i in infolist:
        print i.filename
        f = normalizer(i.filename)
        print f
        dirname = os.path.dirname(f)
        if dirname:
            assert os.path.abspath(dirname).startswith(os.path.abspath(".")), \
                "Security violation"
            if not os.path.exists(dirname):
                os.makedirs(dirname)
        if not f.endswith("/"):
            open(f, 'w').write(archive.read(i))
    archive.close()
if __name__ == '__main__' and len(sys.argv) == 1:
    # Hack for Python 2.x to support unicode source files as doctest sources.
    reload(sys)
    sys.setdefaultencoding("UTF-8")
    import doctest
    doctest.testmod()
    print "If there are no messages above, the script passes all tests."