Most likely your IP is spam-blacklisted, some service providers are notorious for having their subnets blacklisted. To fix this you need to request removal of any IP ranges you're concern from any blacklists they may be in, they will do so after some verifications. Also, you need to authenticate your emails using different technologies like DomainKeys Identified Mail (DKIM), SPF and Sender ID. This is a full time job.
The solution that worked for me is setting Postfix as a proxy. Basically, you make Postfix act like a client that sends emails through a reputable relay service, in my case gmail. You will need to add the following to Postfix configuration file, main.cf :
smtp_sender_dependent_authentication = yes sender_dependent_relayhost_maps = hash:/etc/postfix/sender_dependent_relayhosts relayhost = [smtp.gmail.com]:587 smtp_use_tls=yes smtp_sasl_auth_enable = yes smtp_sasl_password_maps = hash:/etc/postfix/sasl_passwd smtp_sasl_security_options = noanonymous smtp_sasl_tls_security_options = noanonymous
You will also need to create the map files and hash them:
/etc/postfix/sasl_passwd:
# per-sender authentication account1[@]gmail.com account1[@]gmail.com:passwd1 account2[@]gmail.com account2[@]gmail.com:passwd2 # default relayhost [smtp.gmail.com]:587 default_account[@]gmail.com:default_passwd
/etc/postfix/sender_dependent_relayhosts:
account1[@]gmail.com [smtp.gmail.com]:587 account2[@]gmail.com [smtp.gmail.com]:587
Hash the maps files:
postmap sasl_passwd sender_relay
A reputable relay service ensures your emails are not classified as spam. Good luck!