How do I configure reverse DNS for a SMTP server [duplicate]
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 /etc/postfix/main.cf.
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 64.85.168.249
[dave@odessa ~]$ host 64.85.168.249
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.
Check if the IP address you are using for outgoing SMTP has a DNS PTR record ("Pointer Resource Record"). Not every IP address has a corresponding PTR record, despite the fact that it's recommended in RFC 19212.
You could check the PTR record using an online service, like DNSReport.com. There is a box "IP Information" on the first page.
The second case you mentioned seems to be a temporary problem, probably of the receiving SMTP server.
In an effort to curb incoming spam, many mail servers these days do a "reverse DNS lookup". That is, they take a look at the IP address connecting to them and then try and do a reverse DNS lookup to see if there is ANY response.
This prevents any random IP address from becoming a mail server and sending out thousands and thousands of emails.
Some mail servers even go an extra step and have additional points/verification based on WHAT the reverse DNS came back with. For the most part, if you have any sort of reverse DNS set up for your IP you'll be "okay".
If you don't have control over the reverse DNS for your IP address contact your ISP and ask them to create a reverse DNS record (ie. PTR record) for the IP address that is sending out your email.
Alternatively, you could opt to use a mail server (which has a reverse DNS record already in place) or you could use your ISP's mail server and relay your mail through them.
Hope this helps.