First of all you can use Expression.MessageId instead of Expression.Header
List<long> uids = imap.Search(Expression.MessageId(email.MessageID));
How to search for all emails that have Message-Id set
All emails should have Message-Id header or the other way around: if an email doesn't have this header, it means it isn't a valid email message.
To search for all email that have particular header you should use this code:
List<long> uids = client.Search(Expression.HasHeader("any-header"));