My mailserver once had some issues on sending messages to different providers.We only allow evidently commercial or similar operators to connect to our mailservers. That's so strange policy to permit only commercial company to send messages to them.
Did you host your mail server in a data center or at your residence? Mail coming from a residential internet connection may be seen as spam.
