Is your server hosted on a dynamic IP? Most dynamic IPs are blacklisted nowadays. You can use relaying in that case: http://www.howtoforge.com/postfix_relaying_through_another_mailserver