Во-первых, не ожидайте, что заголовок Message-Id будет глобально уникальным. Любой хакер может легко создать свое собственное сообщение и повторно использовать известный Message-Id, чтобы попытаться запутать программное обеспечение, которое зависит от уникальности Message-Id.
При этом вам нужно будет использовать IMailFolder.Search()
API в сочетании с SearchQuery.HeaderContains()
для поиска сообщений с определенным заголовком Message-Id.
var uids = folder.Search (SearchQuery.HeaderContains ("Message-Id", "blah@blah.com"));