Legal! Consigo acessar smtp.gmail.com - essa foi uma ideia inteligente. O Mailgun está definitivamente bloqueando esse endereço de IP específico. O suporte do Mailgun não está sendo muito prestativo, então ainda posso começar de novo com um novo endereço de IP na próxima semana.
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.
Se alguém encontrar este mesmo problema hoje, 
desculpe, nós mesclamos uma atualização de gem que parece ter causado o mesmo problema
Acreditamos que quebrou a partir de:
e foi corrigido a partir de: