Problema con servidor y Formulario php

[sumde]

Si, la cuestion es que en un servidor se mandaba perfecto pero cuando probaba en correos de gmail y outlook por ejemplo, no los mandaba. Era el mismo codigo exactamente lo mismo, en el servidor donde se aloja el sitio llegaban sin problema, pero cuando probaba en estos de gmail nada. Sí que revise en spam y nada. Y es que mis pruebas las realizaba con correos de gmail, como no llegaban entonces crei que algo tendria mal en el codigo, pero luego lo cambie de correo al del dominio y funciono correcto. No entiendo qué ocurre.

Probaré lo que me dices de los headers. Y vengo con el resultado.
Mil gracias por su tiempo.