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.
Must = external requirement
I cannot fathom how you think should* would act as a requirement in any sense of the world.