Viva.com, one of Europe's largest payment processors, sends verification emails without a Message-ID header — a requirement of RFC 5322 since 2008. Google Workspace rejects them outright. Their support team's response to my detailed bug report: your account has a verified email, so there's no problem.
My favorite is when you do “first.last+company@domain.com” and they come back saying it’s an invalid email. But “first.last+somethingelse@domain.com” works just fine. Meaning they are looking for their company name in the email and hard failing on it.
The one I am thinking of in particular also failed with “company@domain.com”.