Hmm,
The problem was supposedly from what’s called Sender Protection Framework, where some email systems check to verify if a server is authorized to send email from a domain.
I updated this in the DNS records and that should have fixed it, it did seem to cut down on this problem. But not completely.
Need to try something different.