Sinceramente ho appena finito un ambiente gestionale in php e genero una marea di mail per notifiche agli utenti, ho usato la funzione come dicono su php.net (alias come ho scritto sopra) e tutto funziona in maniera corretta.
Il problema potrebbe anche essere da un'altra parte, e cioè nel sender fisico della posta.
Se usi un server linux, la funzione si appoggia a sendmail e funziona correttamente, se usi un server windows esiste una copia di sendmail ma non è efficace quanto l'originale.

Questo è un codice simile a quello che uso io:

$to = "info@domain.it";
$subject = "oggetto";
$message = "messaggio da inviare";

$header = "From: info@domain.it" . "\r\n" .
"MIME-Version: 1.0" . "\r\n" .
"Content-Type: text/plain; charset=UTF-8" . "\r\n" .
"Content-Transfer-Encoding: 8bit" . "\r\n";

mail($to, $subject, $message, $header);

Le aggiunte del Mime type e dell'encoding utf-8 non è necessaria, io la uso insieme ad altre funzioni per gestire le lettere accentate

Comunque se hai risolto tanto meglio per te