[Arnt]

If you read RFC 2119, you'll see that the definition of SHOULD includes the word must. Perhaps it's easier to understand if I rephrase it as: "If you understand the issue and its consequences, SHOULD means optional. If you don't, SHOULD is equivalent to MUST."

Message-ID has maybe half a dozen types of problem. If you know all of them, leaving it out is up to you.