La pagina che invia i dati deve avere il charset impostato correttamente, per sicurezza usa sia l'HTTP header (nel file php) che il meta tag http-equiv...

Inoltre se vuoi evitare le rogne "organizzative" usa phpmailer. Ottima libreria, ben fatta e ben scritta. Basta sbagliare anche solo un carattere o un \t...

Ciao, vorrei consigliarti di leggere qui: http://www.php.net/manual/en/function.mail.php visto che posso solo pensare a come è costruita, ma se non mi dici...