This is what I ended up doing.
The suggestion to use the IMAP service is absolutely correct. The trick is not to pull in all your mail, but use the features of IMAP to retrieve only the information you are interested in. In our case, that is the "Delivered-to:" header.
The entire process only takes a few minutes on a full gmail account.
import imaplib
# Login to IMAP and get ALL message IDs.
mail = imaplib.IMAP4_SSL("imap.gmail.com")
mail.login('xxxxxx','yyyyyy')
mail.select("[Gmail]/All Mail")
result,data = mail.search(None,"ALL")
ids = data[0]
id_list = ids.split()
# Retrieve the delivered-to headers in chunks of 100 and output them
while len(id_list)>0:
nowlist = id_list[:100]
id_list = id_list[100:]
result, data = mail.fetch(",".join(nowlist),'(BODY.PEEK[HEADER.FIELDS (DELIVERED-TO)])')
for dt in data:
if len(dt) == 2: # We actually have such a header
if ":" in dt[1]: # And it's not empty
print dt[1].split(":")[1].strip() # print the address