You can set `message-generate-headers-first' to t and see what headers Message produces when you start editing a message.Good suggestion: I just tried. Now message-generate-headers-first is true, and Message-ID doesn't appear in the message-required-mail-headers. Result: my emails all have Message-ID header, and it always reflects the value of message-user-fqdn!
Allow me to make a precision here; my emails *as received* have Message-ID, but when editing before send, the header is not there.
