Returned mail to outside domains

Hey guys,
I've been having a problem when several outside domains try to send mail to my server, namely people sending mail from woway.com.
While other outside domains like gmail are fine.

We can send to them fine but when they try to reply or send to us they get an error returned as follows.

----------------------------------------------------
This message was created automatically by the mail system (ecelerity).

A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:

>>> name@mydomain.org (while not connected): 554 5.4.7 [internal] exceeded max retries without delivery
This message was created automatically by the mail system (ecelerity).

A message that you sent could not be delivered to one or more of its.
---------------------------------------------

Any ideas as to whats creating the error or how to solve it?
I just have no idea whether it's on my end or the senders.

Everything looks ok on my end such as DNS and my MX records, nothings getting stuck in the ques and there are no error in the logs.
Please help....
and thanks.
  

Sounds like a potential DNS issue on their end.

Pat Richard MVP
Plan for performance, and capacity takes care of itself. Plan for capacity, and suffer poor performance.
http://www.ucblogs.net/blogs/exchange/
 

That's what I was thinking.
We had no issues up until recently.
I did notice that their addresses changed from name@email.domain.edu to say name@domain.edu, at this point we started having problems.
My guess is they changed their domain and forgot to =set up their DNS with the ISP.
I guess I'll have to wait to hear back from them.