サイトを新しいHetznerサーバーに移行したところ、メールが期待どおりに動作するようになりました。メールを壊したのが何だったのか知っている人はいるでしょうか！助けてくれた皆さん、ありがとうございます。いずれにせよ、この経験からトラブルシューティングについて何かを学べたので、時間の完全な無駄ではありませんでした。
Mailgunのサポートは、問題がサーバー固有のものであったと確信しています。影響を受けたIPからのアクティビティは確認されておらず、IPを積極的にブロックしていたわけではないとのことです。