Do you have the various auth headers setup on for your mx records? I have to go through that ordeal occasionally when setting up outgoing emails for sendgrid or mailchimp campaigns. There are some things you can due to reduce the likely hood of mail being auto flagged as spam although in a lot of ways it is out of your hands.