Earlier quoted context omitted.
Are you hosting your own email server?
and if you are rolling your own are you having any issues with spf or spam flags?
There's an odd email server here and there that suspects anything that isn't gmail, there was even a mail server once that required me to prove I exist, but those are very few, and normally single user installations.
The secret is that besides not sending spam, you must receive email. If you don't get enough email, other servers start suspecting you. And, of course, there are configuration problems - since I'm writing my own mail server, I get a few of them, but even on standard software you have to make sure you set it correctly.