Я не вижу простого способа сделать это в Gmail.
Решением было бы загрузить почту на настольный клиент (с POP или IMAP), например, Outlook, потому что это легко для сценариев с VBA. А затем проанализируйте каждую почту с VBA и добавьте контакты.
Примерно такой сценарий: http://www.vbaexpress.com/kb/getarticle.php?kb_id=518