Ok ho risolto settando gli Header in questo modo:

Codice PHP:
         $headers  "MIME-Version: 1.0\n"
                
$headers .= "Content-type: text/html; charset=iso-8859-1\n"
                
$headers .= "X-Priority: 1\n"
                
$headers .= "X-MSMail-Priority: High\n"
                
$headers .= "X-Mailer: PHP4\n"
                
$headers .= "From: [email]mail@esempio.it[/email]\n"
                
$headers .= "To: [email]mail@esempio.it[/email]\n"
                
$headers .= "Reply-To: [email]mail@esempio.it[/email]\n"
Grazie della dritta...

Morale della favola (se ho ben capito):

- Alcuni header vanno specificati obbligatoriamante (anche se su php.net sotto la funzione MAIL() li da come "aggiuntivi")

- C'è un ordine esatto in cui dichiararli credo.

Se sbaglio correggetemi eh?

Grazie ancora a Gianiaz.