Exchange/outlook message: Delivery to the following recipients has been delayed.

1. MS KB,the Remote Simple Mail Transfer Protocol Service Rejected AUTH Negotiation
http://support.microsoft.com/kb/329636

2. Ensure Exchange SMTP virtual server is configured properly
Open your Exchange System Manager Console
Go to Administrative Group ==> Domain ==> Servers ==> Server ==> Protocol ==> SMTP
Right click on "Default SMTP Virtual Server"
STOP service
wait for couple of seconds
START service

3.Ensure local DNS is configured properly
It can be that the exchange server could not find any DNS servers.
Please edit the SMTP protocol in delivery - advanced - configure external DNS servers with your dns server of the ISP.
If after this all the messages should get out, then the problem is with your local dns server.

3.Test target mail server
Usually, this indicates a problem on their end. Perhaps the mailbox is full or their mail server is down. However, if you are able to send mail to those addresses from other accounts (Hotmail, Yahoo, etc.), but not your Exchange server account, then there could be other issues.
I am assuming that your mail server is Microsoft Exchange.

Common causes include:
- The recipient's mailbox is full. Usually, though, you would get a different error message.
- The address is invalid.
- Your mail server is on a blacklist. This can happen if you have an open relay, or if you are using dial-up (many sites block mail coming directly from known dial-up IP addresses). There are other ways to be added to public blacklists.
- Their mail server is on a blacklist. Exchange does not include the feature to check against blacklists, but there are third-party add-ons which can do this, such as antivirus and antispam software.
- A firewall is blocking access to their mail server. This could be your firewall or theirs.
- There are other routing problems between your server and their server.
Try the following.
- Open a command prompt.
- Type "NSLOOKUP" and press enter.
- Type "SET TYPE=MX" and press enter.
- Type in the domain name of the address that is giving you problems. For instance, if you are trying to send to BillGates@microsoft.com, you would type "microsoft.com" and press enter.
- A list should appear. This is a list of the mail servers (DNS MX records) that are assigned to that computer.
- Look for the server name with the lowest preference number. If they are all the same preference, just use one. In our example, it is maila.microsoft.com.
- Type "exit" and press enter to quit NSLOOKUP.
- Try to ping the address.
- If successful, try to connect to the mail server manually:
- Type "telnet maila.microsoft.com 25" and press enter, substituting the appropriate server name.
- You should see a server banner message (see example).
<<<>>>
- Type "HELO" and press enter (you might not see what you type. This is normal).
- Type "mail from:" substituting your address and press enter.
- Type "rcpt to:" substituting their address
- Type "data" and press enter.
- Type "Subject: Test message" and press enter TWICE.
- Type a short message. When you are done, press enter, type a period, and press enter again to end the message.
- Type "quit" and press enter to exit.
NOTE: If everything works, then the message will be sent to the address.Keep an eye out for any error messages during this process.Your session should look like the following:

---------------------------------
C:\>nslookup
Default Server: somednsserver.whatever.zzz
Address: 192.168.0.5> set type=mx
>microsoft.com
>Server: somednsserver.whatever.zzz
Address: 192.168.0.5microsoft.com MX preference = 10, mail exchanger = maila.microsoft.com
microsoft.com MX preference = 10, mail exchanger = mailb.microsoft.com
microsoft.com MX preference = 10, mail exchanger = mailc.microsoft.com
maila.microsoft.com internet address = 131.107.3.125
maila.microsoft.com internet address = 131.107.3.124
mailb.microsoft.com internet address = 131.107.3.122
mailb.microsoft.com internet address = 131.107.3.123
mailc.microsoft.com internet address = 131.107.3.121
mailc.microsoft.com internet address = 131.107.3.126

>exit

C:\>ping maila.microsoft.com
Pinging maila.microsoft.com [131.107.3.125] with 32 bytes of data:
Reply from 131.107.3.125: bytes=32 time=91ms TTL=50
Reply from 131.107.3.125: bytes=32 time=87ms TTL=50
Reply from 131.107.3.125: bytes=32 time=88ms TTL=50
Reply from 131.107.3.125: bytes=32 time=87ms TTL=50
Ping statistics for 131.107.3.125:
Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 87ms, Maximum = 91ms, Average = 88ms
C:\>telnet maila.microsoft.com 25
220 inet-imc-01.redmond.corp.microsoft.com Microsoft.com ESMTP Server Tue, 18 May 2004 14:57:17 -0700helo
250 nasmail02.psi.premier-system.com Hello [192.168.0.24]
mail from:testing@bogus.zzz
250 2.1.0 testing@bogus.zzz....Sender OK
rcpt to:billgates@microsoft.com
250 2.1.5 billgates@microsoft.com
Data
354 Start mail input; end with .
Subject: Test messageThis is a test.250 2.6.0 Queued
mail for delivery
quit
221 2.0.0 maila.microsoft.com Service closing transmission channel
Connection to host lost.
C:\>
---------------------------------


http://www.experts-exchange.com/Software/Server_Software/Email_Servers/Exchange/Q_23890828.html