The RFC says a SHOULD is to be treated like a MUST, but well-justified exceptions are allowed.

Per RFC2119: 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.

So, it's fairly explicit that the sender should use message-id unless there's a good reason to not do so. The spec is quiet about the recipients behavior (unless there's another spec that calls it out).