Para qualquer outra pessoa que se depare com isso, o que finalmente funcionou para mim (embora não de forma compreensível):
Desativar e reativar meus servidores MX parece ter resolvido o problema.
Para qualquer outra pessoa que se depare com isso, o que finalmente funcionou para mim (embora não de forma compreensível):
Desativar e reativar meus servidores MX parece ter resolvido o problema.