Problem sending emails issue

Ok. So I have this dedicated server on which emails work fine for all except one customer. They have 35 odd email ids and do a lot of email exchanges as they are a placement agency. They have contacts in Saudi Arabia. Recently the client started complaining that the emails sent to Saudi contacts are not getting delivered. Their emails are received by everyone else except those in Saudi.. What kind of sorcery is this? What's the issue?