This sounds very much like an issue with SPF and/or DKIM for your domain. I try to explain some of the technical details here: