Eu encontrei o problema. O roteamento confuso de mensagens entre sites entre servidores de e-mail, que alteramos para conexão de internet de backup durante a interrupção, não foi alterado novamente. Isso estava entupindo a fila com o tempo limite, porque eu não tinha voltado ao roteamento normal. O correio só estava sendo entregue internamente em uma direção.
Agora estamos enviando e-mail com 100% da nossa capacidade de largura de banda:)