POP3 – UIDL is a required command
hackensplat.com
hackensplat.com
In practice, it is pretty reliable -- even when it is not set by the sender, most MTAs will add it if missing. So your origin "sendmail" will generate one, and failing that, the smart host will, and failing that, recipient's MTA will. And the common format often includes GUID or high-precision timestamp, so the collisions are pretty unlikely.
It was meant to send one email every day. Until it wasn't.
I know that practically, we want to support every email out there, even if it is not quote RFC compliant -- but how far do we want to go? Is it worth adding all new mechanism just because someone out there may be sending non-compliant messages? Especially given that those non-compliant messages are likely to break other things like mail databases, IMAP UIDVALIDITY and so on?