Eu não aceitaria a palavra da CenturyLink de que eles não estão filtrando a porta 25. A porta de bloqueio 25 é uma medida muito comum adotada pelos ISPs para evitar que máquinas "botted" sejam usadas para enviar spam. O servidor SMTP que você está usando também permite a porta 587? 587 é o padrão para envio agora. Vale a pena tentar antes de qualquer solução de problemas mais avançada.
Você sabe que não pode se conectar na porta 25, mas não sabe onde essa conexão está falhando. Uma boa maneira de descobrir isso é com um traceroute TCP. Em resumo, você poderia iniciar uma instalação do Linux (ou live cd) e fazer dois traceroutes da seguinte maneira (alterar o nome do host conforme apropriado):
[root@gamma ~]# traceroute -T -p 25 smtpserv.uri.edu
traceroute to smtpserv.uri.edu (131.128.1.40), 30 hops max, 60 byte packets
1 Wireless_Broadband_Router.home (192.168.1.1) 1.093 ms 1.092 ms 1.090 ms
2 lo0-100.PRVDRI-VFTTP-303.verizon-gni.net (100.40.70.1) 6.626 ms 6.628 ms 6.626 ms
3 T1-5-0-2.PRVDRI-LCR-22.verizon-gni.net (100.41.218.154) 9.452 ms T1-5-0-3.PRVDRI-LCR-21.verizon-gni.net (100.41.218.156) 10.893 ms T1-5-0-2.PRVDRI-LCR-22.verizon-gni.net (100.41.218.154) 9.441 ms
4 * * *
5 * * *
6 * * *
(no replies after this point)
[root@gamma ~]# traceroute smtpserv.uri.edu
traceroute to smtpserv.uri.edu (131.128.1.40), 30 hops max, 60 byte packets
1 Wireless_Broadband_Router.home (192.168.1.1) 1.248 ms 1.241 ms 1.239 ms
2 lo0-100.PRVDRI-VFTTP-303.verizon-gni.net (100.40.70.1) 9.302 ms 9.305 ms 9.303 ms
3 T1-5-0-3.PRVDRI-LCR-21.verizon-gni.net (100.41.218.156) 13.585 ms T1-5-0-2.PRVDRI-LCR-22.verizon-gni.net (100.41.218.154) 12.165 ms T1-5-0-2.PRVDRI-LCR-21.verizon-gni.net (100.41.218.152) 13.582 ms
4 xe-3-0-8-0.BOS-BB-RTR2.verizon-gni.net (130.81.163.188) 12.162 ms * xe-11-1-0-0.NY5030-BB-RTR1.verizon-gni.net (130.81.163.180) 16.170 ms
5 * * *
6 0.ae2.BR3.NYC4.ALTER.NET (140.222.229.99) 16.828 ms * *
(etc: this traceroute completes)
O primeiro traceroute está usando a porta TCP 25. O segundo está usando alguma porta UDP aleatória e chega até o destino. O segundo traceroute é o meu controle: ele me mostra que eu posso alcançar com sucesso o host de destino. O primeiro mostra que minhas tentativas de conexão na porta 25 estão morrendo entre os saltos 3 e 4: é onde meu ISP está bloqueando a porta 25.