Receiving NDR - Recipient address rejected: ERS-RBL

Hi,

One of our clients have been receiving a lot of Spam so we implemented Microsoft Exchange Online Protection to filter their emails.

We now have some issues where some users cannot send to a couple of domains they get a bounce backl as shown below;

 <Recipient Email Removed>
 
in05.hes.trendmicro.eu gave this error:
<Recipient Email Removed>: Recipient address rejected: ERS-RBL.
 
Your message wasn't delivered due to a permission or security issue. It may have been rejected by a moderator, the address may only accept e-mail from certain senders, or another restriction may be preventing delivery.
 
 
 
 
 
 
 
Diagnostic information for administrators:
 
Generating server: SBS2011.DiamondExhibitions.local
 
<Recipient Email Removed>
in05.hes.trendmicro.eu #550 5.7.1 <Recipient Email Removed>: Recipient address rejected: ERS-RBL. ##
 
Original message headers:
 
Received: from SBS2011.DiamondExhibitions.local ([fe80::3d91:cd4c:256a:da06])
 by SBS2011.DiamondExhibitions.local ([fe80::3d91:cd4c:256a:da06%14]) with
 mapi id 14.01.0438.000; Mon, 27 Oct 2014 15:25:50 +0000
From: Lewis Hopkins <lewis@diamondex.co.uk>
To: <Recipient Email Removed>
CC: Oscar Morgan-Windsor <oscar@diamondex.co.uk>
Subject: RE: Exhibition Stuff
Thread-Topic: Exhibition Stuff
Thread-Index: Ac/x2PpwffKBPU+pTtahDwC64ARfWgAIURTw
Date: Mon, 27 Oct 2014 15:25:49 +0000
Message-ID: <1C6D17BEBFE4984DACF66B8946BA11A3355314D3@SBS2011.DiamondExhibitions.local>
References: <ADE23B3C2120B342A8329B07180BB86630A510C4@THERMSBS2011.tgl.local>
In-Reply-To: <ADE23B3C2120B342A8329B07180BB86630A510C4@THERMSBS2011.tgl.local>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [192.168.16.28]
x-tm-as-product-ver: SMEX-10.5.0.1057-7.000.1014-20378.004
x-tm-as-result: No--60.005400-5.000000-31
x-tm-as-user-approved-sender: No
x-tm-as-user-blocked-sender: No
Content-Type: multipart/related;
        boundary="_007_1C6D17BEBFE4984DACF66B8946BA11A3355314D3SBS2011DiamondE_";
        type="multipart/alternative"
MIME-Version: 1.0


I have checked they are not listed on any blacklist, Microsoft have also checked the configuration for Exchange Online Protection which they say is good, there is no problems with them.

Can you help me?