An internal DNS error caused a failure to find the remote server indicates that the remote domain has no available MX record. Use NSLOOKUP to locate the remote domain’s MX record
If you find the MX record, use TELNET to communicate to the remote domain (Ex: telnet server.domain.com 25) on port 25. This is the same as if Exchange is talking.
Next, use Q153119 (http://support.microsoft.com) to send a test message.
If that fails, try using Netmon to see the communication process.
Be sure that all SMTP Virtual Servers are default value, that there is no SMTP connectors installed, and that there are no 3rd party applications running.
Hope this helps…
If it was working previously try stopping and restarting the SMTP virtual servers also.
<b>I got it fixed.</b>
The issue was that the IIS services had been removed from the services MMC (Not showing up at all). This included the IISSVC,SMTPSVC and the WWWSVC. Getting it removed was somewhat involved. The first thing I had to do was remove IIS all together from the box using the add and remove windows components. Once it was gone, I restarted the box. I then re-installed SP2 for Windows server 2003 and rebooted again. Once that was done, I reinstalled IIS, SMTP and WWW. Once that completed and I verified that those 3 services were running, I checked the exchange queue and saw that the retry was gone and the state was showing ready. I could see the mail coming and going from that queue.