Sporadic SMTP 5.7.1 "Relay access denied" error with Exchange

If users are receiving mail bounced back sporadically with the following message:

 You do not have permission to send to this recipient. For assistance, contact your system administrator. <[server name] #5.7.1 smtp;554 5.7.1 [recipient address]: Relay access denied>

and relaying is configured properly on your server, it could actually be a DNS issue. Login to the Exchange server and lookup the recipient domain:

C:\Documents and Settings\user>nslookup
Default Server: dns.yourdomain.local
Address:  192.168.1.1

> set type=mx
> recipient.com
Server:  dns.yourdomain.local
Address:  192.168.1.1

DNS request timed out.
    timeout was 2 seconds.
*** Request to 192.168.1.1 timed-out

The reason it was timing out is the DNS server included with Windows 2003/2008 enables the EDNS0 extension (RFC 2671) to DNS by default, which utilizes packet sizes greater than 512 specified in RFC 1035. Many firewalls block this by default. For more information:

http://support.microsoft.com/kb/832223 

 My solution was to modify the firewall configuration to increase the packet size. For a Cisco ASA:

fw# conf term
fw(config)# policy-map type inspect dns preset_dns_map
fw(config-pmap)# parameters
fw(config-pmap-p)# message-length maximum 1280
fw(config-pmap-p)# policy-map global_policy
fw(config-pmap)# class inspection_default
fw(config-pmap-c)# inspect dns preset_dns_map 
fw(config-pmap-c)# end
fw#