Generally Message-ID must be unique - no two different messages must ever have the same Message-ID value.
Message-ID header is generated by the client program sending the email.
As you probably realize, email client can put any value as Message-ID and this can't be checked or validated. This means, that at least in theory 2 different emails may have the same id.
Having said that, I've never seen such situation in real live.
Emails with no Message-ID are more common.