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.
# Login to IMAP and get ALL message IDs.
mail = imaplib.IMAP4_SSL("imap.gmail.com")
result,data = mail.search(None,"ALL")
ids = data
id_list = ids.split()
# Retrieve the delivered-to headers in chunks of 100 and output them
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: # And it's not empty
print dt.split(":").strip() # print the address