I'm not sure that this is a good idea.  Here's my reasoning:

Most MTAs will construct a Message-ID for any messages submitted
to them (whether by a local MUA or via port 465 or 587).  The format
of that Message-ID is controlled by the MTA's configuration file,
and can, in some instances, be customized.  Here's an example
from sendmail on OpenBSD:

	Message-Id: <202408300037.74U0bamo012837@bleep.example.com>

This Message-ID includes a timestamp, the queue ID, and the
fully-qualified canonical name of the host.  It is thus guaranteed to
be unique across the universe of all mail messages on all hosts -- an
important property of Message-IDs.  And by including the timestamp and
the queue ID, this makes it vastly easier to search logfiles for the
message than if it didn't.

This also ensures that every message generated on this host uses the same
format for its Message-ID -- well, unless someone switches MTAs or changes
the format, but these things don't happen often.  This consistency
is also an important property, because rather a lot of monitoring,
log analysis, and auditing (I'll come back to that) depends on it.

If mail(1) includes a Message-ID on messages submitted to an MTA then all
of these functions will be affected -- because MTAs will not generate
a new Message-ID if one already exists.  But mail(1) does not "know", per se,
which MTA is running, nor does it "know" if that MTA's configuration
has customized the Message-ID field, so it has no effective way of
generating a Message-ID which matches the format in use by the local MTA.
(And if it did: it might collide with one generated by the MTA.)

There's also no way to guarantee uniqueness in mail(1) itself -- yes, using
sufficiently high time resolution will help, and appending a sufficiently
lengthy random number will help, but these are not a guarantee -- and that's
bad, particularly for people who are running mail systems with audit
requirements for regulatory and legal compliance.  ("Message-IDs
are very very likely to be unique" isn't a replacement for "Message-IDs
are unique".)  Also consider that mail(1) may be running on multiple
systems within an operation and sending messages whose Message-IDs use
the domain name (not the fully-qualified hostname) on the RHS, and since
those instances of mail(1) don't know about each other, so to speak,
I don't think there's a way to guarantee Message-ID uniqueness.

I think it's better not to have mail(1) get into this: let the MTA
handle it for uniqueness, for consistency, and for logging, monitoring,
and auditing.

---rsk