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
System/Network Administrator
SmarterTools Inc.
(877) 357-6278
www.smartertools.com