Outlook - Cant send mail but can receive :s

[Kezmo]

As title, the office are saying media Wales went down for 24 hours, so we had no email, it's now back up and we are receiving mail but get this when they try to send

the follow recipients could not be reached
joe blogs etc
533 sorry, that domain isn't in my list of allowed rcpthosts(#5.7.1)

 

[mrk]

Something isn't whitelisted or is blacklisted?

Full message header?