Emails not being received from certian domains

One of our customers is having troubles receiving emails form certian domains.  It is not a black and white issue, as sometimes emails come through, sometimes they dont.  SOmetimes they come in slow.

For example, one of our clients users has a mailbox with a few different emails - eg:
first.last@domain.com
firstlast@domain.com
admin@domain.com

If a user from one domain sends to the first address, they will get the below email, however, emails to the 2nd two addresses go through fine.
The other domain that has issues sending seems to mainly (I think) have issues replying to emails.


Delay Report
Your message:       RE:
addressed to:       XXXXXX@XXXXX.com.au

has the following delivery status:       Your message has been delayed due to a temporary network, server, or mail file unavailability. Delivery of your message will be attempted again.
What should you do?
This message is an informational Delivery Status Notification and does not require any further action.
•      Delivery to the recipients indicated above has been delayed.  You do not need to resend this message.  The server will continue to attempt message delivery.