Ciao, non ho la soluzione ma ho il tuo stesso problema.
Nel mio caso la funzione mail() viene riconosciuta dal server e restituisce true, tanto che la condizione che ho posto visualizza "la mail è stata inviata con successo" (in alternativa visualizzerebbe "si è verificato un errore").
Probabilmente il problema è nelle impostazioni delle estensioni Apache+Php: se non è stato configurato un account del server per inviare all'esterno (sul web) il messaggio di posta, questo verrà inviato all'interno (cioè sulla scheda di rete!) e non giungerà mai ad un account reale. Intanto la funzione mail() continuerà a restituire true: una volta che il messaggio è stato inviato, non importa su quale canale (un webmail server oppure una scheda di rete), la funzione viene comunque elaborata senza problemi e restituisce true.
Il problema vero e proprio sarà riuscire ad ottenere il supporto tecnico dal tuo provider, perché se non riscontrerà errori nel file di log probabilmente ti risponderà che il problema è nello script, quindi non è di loro competenza.
A me è successo così e non c'è stato modo di fargli comprendere diversamente.

Hai provato a testare il tuo script su un altro hosting?
Se altrove funziona hai la certezza che si tratta di un problema di server.

Ti sei sincerato di avere i privilegi per modificare le impostazioni dei files .ini di php e Apache?
Se non le puoi modificare è inutile visualizzare phpinfo()

Ciao.