Problema al enviar correos a cuentas terra.es/teleline.es

Alguien sabe a que puede deberse que todos los mails que envio a cuentas de telefónica me son devueltos sistemáticamente, diciendo:

La(s) siguiente(s) direccion(es) fueron rechazadas:

mailquesea@terra.es
Connection timed out:
retry timeout exceeded

lo he probado desde servidores de correo de mis dominios, el de ya.com, un servidor local y siempre ocurre lo mismo. Por supuesto, mis mails llegan a todo el resto del mundo, excepto a los usuarios de terra

Sin embargo, si las cuentas origen y destino son de terra, parece que si llega.