Martin, this behavior might indicate that GMail believes the domain is hosted on their side. Was this domain name ever on a GSuite account by chance? If not, I'd be on the lookout for an improperly configured outgoing gateway. Hope that helps!
Kyle Kerst
Lead Internal Network/System Administrator
SmarterTools Inc.
smartertools.com