Já que perguntar como fazer isso via GMAIL está fora do tópico (veja webapps ), eu vou responder como fazer isso em um cliente de email. Neste caso, o Outlook. Eu mantive isso bastante aberto para que ele se aplique às versões mais antigas do Outlook.
Adicione uma nova conta no Outlook - baixe todas elas via POP3. Certifique-se de não excluí-los do servidor (existe uma opção para isso).
Crie uma nova pasta no Outlook.
Execute uma pesquisa no Outlook para a string que você deseja pesquisar. Arraste todos para a nova pasta.
Exporte para um arquivo e escolha CSV. A partir daqui, selecione esta nova pasta.