I'd start with making sure that SPF and DKIM is setup properly on the sending mail server.