DNS reverso

[Datacenter1]

Par de consejos:

Tu proveedor efectivamente ha colocado un PTR, pero al parecer tu hostname no resuelve a la ip del servidor, lo que está diciendo el soporte de tu proveedor es que debes crear un registro A de tu hostname a la IP del servidor algo como:

31xx37-www1.xxxxx.com ---> IP_Principal mediante un registro A

Adicionalmente hotmail se fija mucho en los registros SPF

Otra opción más sencilla es no usar sendmail sino envíar el correo vía SMTP autentificado, es decir usaras Google para enviar los correos desde php en tu servidor, cualquier mailer de php puede hacer esto