sendmail に特化した話ではないのですが、 MTA 総合スレッドが見つからなかったのでここに書き込みさせてください。
RFC2822では Message-ID の満たす要件として、
The message identifier (msg-id) itself MUST be a globally unique identifier for a message. The generator of the message identifier MUST guarantee that the msg-id is unique.