Delivery has failed

I have SBS2011 network. When users send email out, they get a lot of these message back:
Message 1
From: Microsoft Outlook
Sent: Thursday, October 30, 2014 11:56 AM
To: Mike
Subject: Undeliverable: RE: Martinez
Delivery has failed to these recipients or groups: (
The server has tried to deliver this message, without success, and has stopped trying. Please try sending this message again. If the problem continues, contact your helpdesk.
Message 2

From: Microsoft Outlook
Sent: Thursday, October 30, 2014 12:20 PM
To: Mike
Subject: Delivery delayed:RE: Halloween
Delivery is delayed to these recipients or groups: (
Subject: RE: Halloween
This message hasn't been delivered yet. Delivery will continue to be attempted.
The server will keep trying to deliver this message for the next 1 days, 19 hours and 57 minutes. You'll be notified if the message can't be delivered by that time.


The problem domains are, not limited to,,,,

This network has been black-listed multiple times in recent days, so we actually get "undeliverable" emails back with specific message saying IP address "xx.xx.xx.xx" is in black list somewhere. But the messages above is purely talking about "delay".
Where should I look to begin troubleshooting this issue?
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Simon Butler (Sembee)ConsultantCommented:
Those are connection timeouts.
If you were being blacklisted then they would bounce immediately and return with errors.

The first thing you need to do is look in the queue viewer and see whether there is anything more in there when the messages are delay.

Then you need to see if you can connect to the MX record using telnet to port 25.

As it is multiple domains, the most likely problem is a routing issue, which you will need to take up with your ISP. The telnet test will confirm connectivity.


Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Jerry MillsCommented:
Additionally you could be rate limited by the receiving mail server.  Make sure your mail server is reverse DNS is correctly in DNS zone.   Make sure SPF record and default domain key is being used.

Test your mail server at:
Asif BacchusI.T. ConsultantCommented:
I did notice that those messages are coming from Outlook directly and not Exchange.  I totally agree with Sembee but I would also verify the connectivity of your Outlook clients to the Exchange server itself.  Perhaps you have some internal DNS or other routing issues within your LAN?  Do you have any other problems accessing shared resources or your server in general?  Do you have problems pinging the Exchange server ever?
Big Business Goals? Which KPIs Will Help You

The most successful MSPs rely on metrics – known as key performance indicators (KPIs) – for making informed decisions that help their businesses thrive, rather than just survive. This eBook provides an overview of the most important KPIs used by top MSPs.

sgleeAuthor Commented:
I will respond and answer the questions later tonight or tomorrow morning.
Md. MojahidExchange server admin Commented:
This is caused by your Autocomplete cache in outlook trying to reference the deleted object for the group instead of the new mailbox. You can fix this by either adding an X500 email address to the Mailbox that matches this string:

Alternatively you can clear that entry in your Autocomplete cache by typing out the address and clicking the X button next to the entry that pops up when you do that.
Asif BacchusI.T. ConsultantCommented:
@Md.Mojahid I was under the impression that x.500 was largely deprecated?  Though I do agree that the autocomplete cache should be purged of old entries.  However, I would suggest using NK2 utilites from nirsoft instead of manually trying to delete autocomplete entries since it's faster.

In my opinion, I would still be checking network connectivity as per my previous comment and Sembee's comment.
Simon Butler (Sembee)ConsultantCommented:
I completely disagree with @Md.Mojahid this this has anything to do with the auto complete information, and wonder if the answer has been placed in the wrong question.
The NDR that is returned for auto complete problems is completely different.

Furthermore ignore the references to Outlook in the NDR. That doesn't mean the problem is with Outlook at all, it is just Outlook is the tool rendering the message. The references to Outlook are an attempt to make the NDR more friendly.

Asif BacchusI.T. ConsultantCommented:
@Sembee:  That's interesting.  Whenever I've run into these messages with Exchange deployments, the Outlook reference usually means it's at the client level and if it's something with the server I get the message from the Exchange Admin.  Perhaps I will look into such errors in the future more carefully.  Thanks for teaching me something, I love this site!

@OP: Sorry, didn't mean to hijack your thread, just wanted to thank Sembee!  I think Sembee's first comment is still the best way to proceed.
Jerry MillsCommented:
You are definitely experiencing mail jail.  Mail server may have accepted your email for delivery but it can't deliver the mail at the domain.  Depending on how long mail server is configured to attempt said delivery determines when it gets bounced back to you.  Mail server will hold the email for XX days if it can't contact destination which is what Sembee mentioned with routing issues.

Normally routing issues are resolved locally in your out-bound mail server which is where the email will be stuck.

What are you using for outbound mail service?

Lots of other reasons also possible.  Mail server can be using different configurations as each mail administrator makes his own choices and filtering services.


You will find a email header analyzer that might shed light on you issue.  Copy the pertinent email header and paste into the analyzer.

Regarding port 25 not all mail servers permit anonymous telnet sessions.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.