Problema al enviar emails a telefonica.net y terra.es

Hola,
No entiendo que pasa, pero clientes de terra.es y de telefonica.net han dicho que no han recibido nuestros emails.

Como tengo cuentas antiguas tanto de terra.es y de telefonica.net he hecho pruebas, y es verdad, a veces llegan los emails y otras no llegan.

Lo que no entiendo que los que no llegan no me vienen de vuelta.

He hablado con mi host y dice que el problema tiene que estar en telefonica.
He intentado hablar con telefonica, pero como no tengo el adsl con telefonica no me quieren atender, despues de explicar que llamo como representante de mis clientes que si son clientes de telefonica, me han atendido..."algo", lo único que dicen es que hable con mi cliente de correo, o sea el host.
Este problema lleva ya varios dias, a lo mejor lleva más y no lo sabía yo.
Alguien tiene alguna idea?