> Also, the author was able to get their mail delivered to a personal gmail.com address. The issue was with a Google Workspace custom email domain. This further makes me think of this as a security/spam related issue. Google is clearly capable of processing the message without a Message-id, they are just refusing for business customers.

That's the annoying part to me.

An email is an email. By applying different rules for rejection on different mailboxes, gmail creates a system where it's harder for would-be implementers to test compliance.

If tomorrow gmail creates a new type of mailbox, will there be a third set of rules to have your message delivered?

There are dozens of spam and security settings that admins can change in the Google Workspace console, presumably because different businesses have different requirements. So in practice, there's not just two sets of rules in gmail -- there's probably thousands or millions (however many combinations of settings are actually in use).

Other anti-spam implementations also punish the lack of Message-ID. There are tools online that highlight this as an issue.

This here is a trivial case of simply not testing deliverability at all.