RFC 2822 says "Though optional, every message SHOULD have a "Message-ID:" 
field.  Note the capital 'D'.

Mailx does not write any message ID, but the local receiving Exim/Sendmail
adds a "Message-Id:", notice the lower-case 'd', with ID identifying the
host.

Exim does not create ANY Message-ID: at all if you just connect to SMTP
port and feed it a message.
(Exim always uses a message-id, it needs one to uniquely identify 
messages, but that ID often does not get written to the message, and I
think that it may be entirely independent of the Message-ID: message field.