> isn't a valid excuse to reject a client either.

Yes it absolutely is: https://www.rfc-editor.org/rfc/rfc2119 is quite clear.

    3. SHOULD   This word, or the adjective "RECOMMENDED", mean that there
       may exist valid reasons in particular circumstances to ignore a
       particular item, but the full implications must be understood and
       carefully weighed before choosing a different course.

If the server has considered fully the implications of not having a Message-ID header, then it MAY continue processing.

In general, you will find most of the Internet specifications are labelled MUST if they are required for the protocol's own state-processing (i.e. as documented), while specifications are labelled SHOULD if they are required for application state-processing in some circumstances (i.e. other users of the protocol).

You are describing MAY.

“MAY This word, or the adjective "OPTIONAL", mean that an item is truly optional… An implementation which does not include a particular option MUST be prepared to interoperate with another implementation which does include the option, though perhaps with reduced functionality. In the same vein an implementation which does include a particular option MUST be prepared to interoperate with another implementation which does not include the option (except, of course, for the feature the option provides.)”

Note how it explicitly calls out interoperation with implementations that do or do not implement MAY. As a exception that proves the rule, we can reasonably assume that not interoperating with a system ignoring a SHOULD rule is a correct implementation and it is the fault of whoever is not implementing SHOULD.

Hearsay has it that the reason is spam. Spam messages are said to have massively higher chances of minor RFC violations when they arrive at the destination server.