a mi me paso tambien y puse las cabeceras habidas y por haber ... despues de unas pruebas descubri que el dominio del from estaba baneado por gmail, me explico yo ponia como $from=
[email protected] , resulta que por algun motivo xdominio.com estaba bloqueado o baneado o denegado por gmail.... cambie poniendo un dominio ficticio y plash!!!!! funciono .... prueba con eso .. saludos