Firstly, your mail server MUST say
HELO with it's canonical host name, that is the same value as the
hostname command returns when run on the command line. Under
postfix this is the value of the
myhostname variable in
Secondly, the forward and reverse pointers for your server in DNS must match, and must match the hostname value above. For example
[dave@odessa ~]$ host odessa.cheney.net
odessa.cheney.net has address 126.96.36.199
[dave@odessa ~]$ host 188.8.131.52
249.168.85.64.in-addr.arpa domain name pointer odessa.cheney.net.
Thirdly, check that your mail server is not acting as a open relay. If your mail server is configured to relay mail from other hosts, you should be very careful to ensure that those hosts themselves are not open relays, or are properly protected from accepting messages from unauthenticated hosts There are plenty of sites out there that will make a check for you, http://www.checkor.com/ for example.
Lastly, with the large sites, some of our mail will marked as spam, it's just the law of averages. It's your responsibility to make sure you comply with the appropriate regulations for send automated or bulk email, like CAN-SPAM. The most important part of this is a straight forward way for people to unsubscribe from your mailing lists. If you make this hard for people then you're users are more likely to hit the large spam button in their mail client which will be fed back to the mail host and will work against your server.