I’ve had several clients in the last few months report issues with recipients not receiving emails. With the proliferation of SPAM and viruses email admins are coming up with new ways to identify and block unwanted email as cheaply as possible (cheap here meaning with as little system load – CPU, bandwidth – as possible).
Some email systems now require rDNS/PTR entries at the ISP-level to verify the email source is who they say they are, SPF records (a DNS entry for the domain to verify what servers can send mail “from” their domain), and various blacklists (public or privately available lists of either known spammers or potential SPAM locations).
There are various ways to combat each requirement and keep up with the changes needed, however you may find it simpler to use a smarthost or mail-forwarding service. These work by configuring your email server to send all outbound email to that service. The service then takes care of sending your email out and they are responsible for making sure mail is received.
ISPs often provide this service for free for their clients, however a managed service (such as the Outbound Filter service from AppRiver.com) also provides filtering (so you don’t send spam, viruses or sensitive material to clients) as well as advanced management options for a fee.
Note that you may still need a SPF record, but the service provider should provide support for this and it should be a one-time action.
Whoever manages your DNS records can add/edit TXT/SPF records for you.
More on rDNS: http://en.wikipedia.org/wiki/Reverse_DNS_lookup
Note that your ISP needs to configure the rDNS/PTR records.