problemas correo ovh

[living]

Tengo contratado un servicio de hosting con ovh. Lo contraté porque me daban 2 cuentas de correo a muy bajo precio (bajísimo). El problema que tengo es que dependiendo del proveedor desde el que se me mande un correo lo recibo o no. Por ejemplo no recibo ningún correo de hotmail, de telefonica.net,etc. Les escribí contandoles que no recibía muchos de los correos o me llegaban muy tarde y me dijeron que había habido problemas con los servidores pero que ya estaba subsanado pero yo sigo con los mismos problemas.
¿a alguien le ocurre lo mismo?