Exchange 2010 having hiccups sending out at random

I have a SBS2011. been ok for a few months but recently users been having problems sending out, some get this msg back :
-----------------------------------------------------------------------------------------------------------------
From: Microsoft Outlook
Sent: 23 April 2015 00:44
To: User1
Subject: Delivery delayed:Re: from Receipient1

Delivery is delayed to these recipients or groups:

Davis (davis@xxxx.co.uk) <mailto:davis@sxxxx.co.uk>

Subject: Re: Enquiry

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 50 minutes. You'll be notified if the message can't be delivered by that time.
------------------------------------------------------------------------------------------------------

I went through the event viewer but not seeing anything, looking at the error, it seem like it is not routing out, as its all done via DNS, I thought may be this has something to do with the DNS, so I restarted the DNS server, this seem to unblock the outgoings, but then a week later, some users is hitting the same problem again, so it seem like if I restart the DNS Server will cure the problem, but any one know what is the actual cause of this ?

It is a fresh SBS2011 installed 5 months ago, nothing changed on it, I have even removed the AV just to see if its causing the problem or not but still the same.
CombemartinAsked:
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:
Have you made the DNS change outlined in this KB article:
https://support.microsoft.com/en-us/kb/968372

I would also run the SBS BPA against the server and ensure that doesn't flag anything network wise.
You can get the download links from http://sbsbpa.com/

Simon.
0

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
Frans BrouwerSenior Systems AdministratorCommented:
it look like receiving servet is temporarly offline or is not responding.  this should solve itselve
0
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
Exchange

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.