According to RFC2822, messages should have a Message-ID header that uniquely identifies the message. The general format of the value for this header is email@example.com by convention. The right-hand side is easy to figure out, but what about what’s on the left-hand side of the at-sign? There are lots of ways to generate a unique value for the left-hand side, but it’s hard to choose between them.
The first couple that come to mind are MD5 and SHA-1. MD5 is largely being replaced by SHA-1 due to concerns about some attacks on the hash, so it’s easy to choose between those two. UUIDs are also a possibility. Modern mail transfer agents (MTAs) like Postfix seem to use a much more compact value, so I should probably see what they do as well.
It’s also tempting to use time-based values, like the number if milliseconds since the epoch. One would only have to cache values used in the last second to make sure you didn’t reuse any IDs, and that would be a fair amount more compact than a UUID or a 160-bit hash in hexadecimal.
It seems that Postfix uses something based on the message queue ID it assigns to each message (src/global/mail_queue.c), and also uses millisecond-resolution time to ensure every ID is unique. I can’t find Sendmail’s Message-ID code after a quick look, so I’m guessing it’s something that can be defined in sendmail.cf.
I’ll need to do a bit more reading to figure out whether a SHA-1 hash of the current time with milliseconds combined with the sender, recipient, and subject or something similar will do the trick in a portable manner.