>>> type, data = mail.search(None, '(HEADER Message-ID "<firstname.lastname@example.org>")')
I should have mentioned that I'm using python IMAPLIB.
Even though the message-id is valid (there is a message with this ID), nothing is returned. Why? It's just not supported. From google:
Does Gmail support all IMAP features?
Gmail IMAP is a fairly complete implementation of IMAP, but the following features are currently unsupported:
- \Answered and \Recent flags on messages.
- Substring search. All searches are assumed to be words.
- Searching arbitrary headers. Only some headers are available for searches: From/CC/BCC/To/Subject.
- There is no SIEVE interface to Gmail filters.
- Only plain-text LOGIN over SSL tunneled connections are supported.