I've had e.g. foo@mysub.mydomain.com rejected by one of the world's top-3 shipping/courier services. This was on a .com domain registered many years ago, so it wasn't a TLD issue. And the subdomain and its MX was also established long ago. But their software finally did accept the mail address after I removed the "mysub." part. Crazy!