Dicen que está activada pero nunca me envía correos, con varios formularios PHP lo he intentado, incluso en uno que hace la notificación de que sí el PHP lo manda me dice que lo manda, pero los correos nunca llegan.

Heyy?
Pudiste solucionar e implementar bien esta función?, yo estoy en las mismas y no encuentro como lograrlo

Si la función mail() de Php retorna TRUE sólo indica que pudo entregar el mail a la cola del servidor de correos (esto es: correo saliente), este servidor luego deberá enviarlo al servidor destinatario para que finalmente el email sea colocado en la bandeja de entrada del usuario. En esta cadena puede haber diversas fallas, y con cualquier elemento que falle falla el envío del mail.

Para probarlo: háganlo enviando emails a distintos servidores (hotmail, gmail, yahoo, xmail, etc), y constaten donde llego y donde no; puede que hallan sido enviados (revisen el límite de envíos en x tiempo), puede que hallan sido recibidos (o no), puede que los emails desde webcindario estén baneados (esto ya no es una falla sino una regla de politica).

Aunque ningún sistema operativo/lenguaje les permitirá husmear para buscar la falla, una prueba así les permitirá comprender el estado de las cosas.