Most úgy néz ki, hogy megjavult. Különösebb ok nem látszik. Annyi viszont történt, hogy egy partnerünk nyitott ticketet az O365-ben erről, bár a support válaszai alapján nem teljesen ment át mi a probléma. :) Szóval nem tudom, hogy ez valóban segített-e.
A átmenetileg fallback_hosts -al oldottam meg eximben, a megfelelő külső VPS-ünk felé.