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
IT Coordinator
SmarterTools Inc.
www.smartertools.com