Quoting Brook Milligan (brook@biology.nmsu.edu):
> One of my NetBSD machines has recently moved to a new network which is
> behind a firewall.  It now has no publicly accessible DNS entry.
By which you mean the reverse DNS for the address it presents doesn't exist.
...
> I presume that this is because hosts at the receiving end of an smtp
> connection do a DNS lookup and then refuse the connection when they
> cannot find an entry for my machine.  I presume also that the correct
> solution is to obtain a public DNS entry for my machine.
> 
> - Is this correct (or are there better solutions)?
> 
> - Will obtaining a public DNS entry expose the local network to any
>   additional vulnerabilities?

Mail lives on DNS and Network.  Have bad DNS?  No reverse DNS?
Mail will suck.

Putting reverse DNS is NOT a security risk, it's a best practice.

NAT is often over used/misused/seen as a "firewall".

NAT is not a firewall.  NAT is a way to alleviate an IPv4
number limitation.  I've successfully nailed machines through
a NAT connection to show clients this.

However, if you DO have the mail server on a NAT'd network,
you likely want the machine to be able to lookup its real
IP addresses (192.168.1.25) AND you want a reverse DNS
in the PUBLICLY seen DNS so that others can resovle the
connections coming from 128.123.1.2 (or whatever).