Gmail delivery sometimes fails to domain1 but never to domain2, both domains have the same MX, etc

Lets say we have 2 domains, domain1.co.za and domain2.co.za. Both point to the same MX records with the same priority, mx1.isp.co.za and mx2.isp.co.za, both of which send the mail through our ISP's filtering/scanning service. From there, mail for both domains is delivered to our on-premises Exchange server using SMTP. In other words, the routing for messages sent to both domains is exactly the same.

• We are seeing consistent failed delivery of messages sent from Gmail to domain1.co.za, but only for some Gmail users. For some Gmail users, messages are consistently delivered to domain1.co.za.
• On the other hand, messages sent to domain2.co.za are delivered consistently, even when sent by Gmail users whose mail is failing to domain2.co.za.

A bounce message for messages sent to domain1.co.za looks like this:

Delivery to the following recipient failed permanently:

     graeme@domain1.co.za

Technical details of permanent failure:=20
Google tried to deliver your message, but it was rejected by the recipient =
domain. We recommend contacting the other email provider for further inform=
ation about the cause of this error. The error that the other server return=
ed was: 571 571 Server listed in SpamCop RBL (state 14).

----- Original message -----

Received: by 10.182.75.65 with SMTP id a1mr18153847obw.32.1326873881149; We=
d,
 18 Jan 2012 00:04:41 -0800 (PST)
MIME-Version: 1.0
Received: by 10.60.8.3 with HTTP; Wed, 18 Jan 2012 00:04:00 -0800 (PST)
X-Originating-IP: [41.134.138.227]
From: Graeme Donaldson <graeme@bla.bla>
Date: Wed, 18 Jan 2012 10:04:00 +0200
Message-ID: <CAOBQ9=3Dmx674mUAw1E6_gED11rWzwnFUzWBaKpWLVE_xB8-tGjg@mail.gma=
il.com>
Subject: test
To: graeme@domain1.co.za
Content-Type: text/plain; charset=3DISO-8859-1

By contrast, the SMTP headers from a successfully delivered email look like this:

Received: from mx2.isp.co.za (196.x.y.z) by mail.domain1.co.za
 (172.x.y.z) with Microsoft SMTP Server id 14.1.323.3; Wed, 18 Jan 2012
 10:23:23 +0200
Received: from mail-qy0-f175.google.com (Not Verified[209.85.216.175]) by
 mx2.isp.co.za with MailMarshal (v6,8,4,9558)   id <B4f16817a0000>; Wed,
 18 Jan 2012 10:23:22 +0200
Received: by qcsp14 with SMTP id p14so2850129qcs.34        for
 <graeme@domain1.co.za>; Wed, 18 Jan 2012 00:23:21 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=mime-version:date:message-id:subject:from:to:content-type;
        bh=oC4vJzzjAUASBEWdam7JzvNUOB1qoyAUm0ztpK7fjwA=;
        b=I/A2jur39kdKCzu57CHzHzeJNbVqcb/e7WV8SDyulEJTKd942OrM+QYkvF8G5Xwkz4
         ssZ/p/geoqop0dgTAvoCMcdE1escL3UH3ob3k3Vgs4FqH2aKWYT7LqG3Eb53Z4Kl++K8
         D3sD0I8Eb2nZEPLR2pR0K7s8WAtnGb/XgJAws=
MIME-Version: 1.0
Received: by 10.229.76.91 with SMTP id b27mr8321239qck.124.1326875001168; Wed,
 18 Jan 2012 00:23:21 -0800 (PST)
Received: by 10.229.250.66 with HTTP; Wed, 18 Jan 2012 00:23:21 -0800 (PST)
Date: Wed, 18 Jan 2012 10:23:21 +0200
Message-ID: <CANFFNku=7OMQZxXd18LtiA7x7V+uj=wiQkKKdA8F_LhwFwiLVw@mail.gmail.com>
Subject: test
From: User <user@gmail.com>
To: <graeme@domain1.co.za>
Content-Type: multipart/alternative; boundary="001d605b95931b230b04b6c92924"
Return-Path: user@gmail.com
X-MS-Exchange-Organization-AuthSource: exch.ad.local
X-MS-Exchange-Organization-AuthAs: Anonymous

Comparing the SMTP headers, I note that there are 3 "Received:" headers that seem to be entirely within Google's network, with the 4th "Received:" header being the first time it breaks out of Google's network. Looking at the bounce message, it only has 2 "Received:" headers, which makes me think this failure is within Google's network.

Google is notoriously uncontactable for stuff like this so I'm hoping someone else has seen something similar. Has anyone had a similar issue?