Как в Python можно хранить список в памяти, чтобы он съедал меньше этой самой памяти
Мой тест показал, что 1 млн строк (10-13 символов) в питоновском списке занимает около 40 МБ в памяти. Что многовато, но не так уж плохо. 

Протестировал ctypes вот так:
>>> from ctypes import *
>>> FixedSizeStr = c_char*13
>>> MillionStrings = FixedSizeStr*1000000
>>> ms = MillionStrings( *(FixedSizeStr(*str(i)) for i in xrange(1000000)))
Это +215 МБ?!..

Предложенный выше вариант с кодированием в число, хоть и экономит место, но существенно сожрет производительность, если вы будете пробегаться по этому списку и сравнивать с другой строкой.

Так что если вам дейстивтельно нужна оптимизация, то придется писать на С/С++ свой класс и экспортировать в питон. Все остальное будет полумерой.
Может быть, если вас не пугает Си, и вы уверены, что на нем получится компактнее, его использовать его через ctypes, например? С поддержкой такого решения на *nix системах проблем не будет.
Еще один извращенный способ, который пришел в голову — подмонтировать рамдиск через fusepy, создать в рамдиске файл через zlib и ходить по нему seek-ом. :) 
Ну и третий вариант — еще раз подумать. Строки у вас юникодные или ASCII? Нужно ли держать весь список в памяти (это требование производительности?) или приемлемо подгружать очередную порцию, например, фоново, когда текущая подходит к концу?