He movido mi sitio a un nuevo servidor de Hetzner donde el correo electrónico funciona como se espera. ¡Quién sabe lo que hice para estropear el correo electrónico! Gracias a todos los que ayudaron. De todos modos, aprendí algo sobre la solución de problemas con esta experiencia, así que no fue una pérdida total de tiempo.
El soporte de Mailgun está bastante seguro de que el problema era local del servidor. Dicen que no estaban viendo ninguna actividad desde la IP afectada y que no estaban bloqueando proactivamente la IP.