Não, o seu ISP não está bloqueando 25 ou você não conseguirá fazer o telnet para a porta 25.
O que eu descobri é que esse problema está freqüentemente relacionado a erros no DNS. Alguns ISPs (a lista está crescendo) farão diferentes tipos de verificação para verificar se uma mensagem é válida antes de recebê-la. Tenho certeza de que estamos todos familiarizados com a falta de uma pesquisa inversa para um servidor de email, mas alguns ISPs também estão verificando se uma conta de email é válida antes de receber a mensagem.
Essa validação é feita procurando o registro MX de um determinado domínio e, em seguida, verificando o servidor de email listado no registro MX para verificar se o remetente tem uma conta nessa máquina. A maioria dos servidores de e-mail responderá a essa consulta. Quando se sabe que o usuário existe no domínio de email, o email é recebido e entregue na caixa apropriada.
Se o servidor não responder a essa consulta ou a conta do remetente não existir no servidor mencionado no registro MX de DNS desse domínio, a mensagem de erro 554 DNR será emitida.
Verifique seus registros MX e seus registros PTR em seu servidor DNS. Se você tiver mais de um registro MX para domínio, verifique se os registros são válidos e se as prioridades estão definidas corretamente. Isso consertará muitos dos 554 problemas.