Unless your IMAP server is not following the protocol specification, UIDs are assigned by IMAP server in ascending order. That means that emails received later will have higher UID value.
Imap.Search returns UIDs ordered by value.
Now, email can have 2 dates assigned to it:
"Date: " header (IMail.Date) - it is assigned by the sender, it says when email was sent. And as it is set by someone out-of-your control it may be bogus.
IMAP server assigns internal date to every email it receives (Envelope.InternalDate obtained from Imap.GetMessageInfoByUID / Imap.GetEnvelopeByUID).
You can check 2nd to see if UID order matches InternalDate.
I noticed that all emails with wrong dates are invitations, maybe the problem is with the invitations sender? For example it may produce emails with broken "Date: " header (for example using invalid timezone).