I have seen this issue many times now. So I will write this down to remeber it. And hopefully help someone with same issue.
When you try to send mail to some domains you might see that the mail ending up in Exchange queue. With status retry and DNS lookup failure.
The users will get expiring message after the message is experied.
#550 4.4.7 QUEUE.Expired; message expired ##
This is not actually Exchange problem, but DNS server lookup problems. You will probably also get problems with browsing some URL and so on. Some DNS name queries are unsuccessful after you deploy a Windows Server 2003 or Windows Server 2008 R2-based DNS server
I have only seen this problems with Windows 2008 R2 though.
To resolve problems run following command on DNS servers:
dnscmd /config /enableednsprobes 0
Now force Exchange to retry deliver mail if you have mail in your queue.
See : http://support.microsoft.com/kb/832223 for more information