Message-ID header is optional and it looks like you have found a message with missing
See following quote from the RFC 5322.
3.6.4. Identification Fields
Though listed as optional in the table in section 3.6, every
message SHOULD have a "Message-ID:"
It means that when creating a new message you should include the
Message-ID field, but also that every parser should be able to process messages with
Message-ID not set.
Try using this code:
foreach (ImapMessageInfo msg in collection)
if (msg.MessageId != null)
Console.WriteLine("Message has no Message-ID header set.");