Ich habe meine Seite auf einen neuen Hetzner-Server verschoben, auf dem E-Mail wie erwartet funktioniert. Wer weiß, was ich getan habe, um E-Mail zu vermasseln! Vielen Dank an alle, die geholfen haben. Ich habe aus dieser Erfahrung jedenfalls etwas über die Fehlerbehebung gelernt, also war es keine komplette Zeitverschwendung.
Der Mailgun-Support ist sich ziemlich sicher, dass das Problem lokal auf dem Server lag. Sie sagen, sie hätten keine Aktivität von der betroffenen IP gesehen und die IP nicht proaktiv blockiert.