Mudei meu site para um novo servidor Hetzner onde o e-mail funciona como esperado. Quem sabe o que eu fiz para estragar o e-mail! Agradeço a todos que ajudaram. Aprendi algo sobre solução de problemas com essa experiência, então não foi uma perda de tempo completa.
O suporte do Mailgun tem certeza de que o problema era local do servidor. Eles dizem que não estavam vendo nenhuma atividade do IP afetado e não estavam bloqueando proativamente o IP.