My Exchange ( we host our own server ) public IP address changed and now some of the emails are getting bounced back, below is one of the examples, is this really a DNS related issue?
firstname.lastname@example.org on Wed, 18 Apr 2012 13:23:29 -0700
You do not have permission to send to this recipient. For assistance, contact your system administrator.
<exchange001.mycompany.com #5.7.1 smtp;550 5.7.1 This system is configured to reject mail from 12.238.xx.xx [12.238.xx.xx] (DNS reverse lookup failed)>