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!