Antes de postar minha pergunta, passei vários dias solucionando problemas e liguei para as pessoas da minha rede no ISP 4 vezes perguntando sobre:
- Antivírus interferindo no tráfego da porta 25. Várias postagens online sobre isso.
- Bloqueios de porta de firewall. A coisa óbvia, mas descartada, porque eu poderia conectar via telnet apenas os comandos não funcionavam
- Inspeção de pacotes
A resposta toda vez que eu liguei foi: "Não, não estamos fazendo nada disso". Falei com pelo menos 5 pessoas. A última vez que liguei, coloquei o controle remoto no servidor, executei os comandos do telnet enquanto estava no telefone e confirmei o problema. De sua própria máquina, ele não teve problemas para se conectar via telnet.
Ele confirmou que eles estavam de fato fazendo algum tipo de bloqueio no tráfego do ESMPT. Aceitei a resposta acima, mas no caso de alguém ver esses problemas desconhecidos, consulte os administradores de rede sobre as políticas de inspeção de pacotes.