The RFC says a SHOULD is to be treated like a MUST, but well-justified exceptions are allowed.
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).