Las causas pueden ser varias, necesitas acudir a tu proveedor de Hosting para que lo solucionen o te guíen.
Ya cambiaste de proveedor de Hosting y tu problema persiste, si usas un software local como Outlook o thunderbird para el correo, te recomiendo que verifiques si la IP de tu conexión a internet está en alguna lista negra.
Primero ontén tu IP en:
http://cualesmiip.com
Y luego revísala en listas negras:
http://mxtoolbox.com/blacklists.aspx
También puedes revisar la IP de tu servidor en listas negras introdiciendo el dominio de tu web en esa misma dirección.
El listado en listas negras puede ser solo una de las causas, solo tu host te podrá asistir revisando en detalle si hay algún problema de configuración o verificar si el error está en el servidor receptor.
Saludos!