Eu tentaria algo assim com o shell do Gerenciamento do Exchange (ou outra máquina com os cmdlets do Exchange):
Get-MessageTrackingLog -start '[date it started]' -resultsize unlimited | where-object {$_.Sender -like '*theirdomain.com'}
Se isso gerar um monte de FAIL, tente:
Get-AgentLog -startdate '[date it started]' | where {$_.P1FromAddress -like '*theirdomain.com'} | select-object Reason | group-object Reason
para uma explicação do motivo pelo qual o Exchange não os ama. Gotas silenciosas são frequentemente antispam.
Se não houver nenhum registro deles alguma vez tocando no Exchange, eu presumo que algo está errado.