Få kopi av mail-trace for hele domenet deres. Dette vil gi full oversikt over alle mailer inn/ut.
Sjekk få kopi av mail-logger, smtp-auth, og andre logger de har.
Sjekk opp epost-headere på epostene med lesebekreftelse o.l. dette kan gi en pekepinne for hvor de kommer fra.
Kjør en diag sniff fra brannmur hvis dere har utstyr for dette og lytt på SMTP/SMTPS, noe unormal trafikk?


Hvis dere ikke har SPF satt opp for deres domene, KREV det umiddelbart!
https://en.wikipedia.org/wiki/Sender_Policy_Framework
Om mulig få DKIM og DMARC satt opp i tillegg

Bruker dere bare, f.eks outlook fra ett fysisk kontorlokale og webmail, kan dere få leverandøren til å sperre SMTP-relay for noen andre IPer en deres offentlige IP midlertidig til dere finner ut av kilden til problemene.

Mine første idèer uten å kjenne løsningen deres.