Wie hast Du das denn verifiziert, dass PHP daran Schuld ist?
$mail_to = mb_encode_mimeheader ( "vorname_nachnam@example.org" );
mb_language ( 'uni' ); // UTF-8
$result = mail( $mail_to, $mail_subject, $mail_body, $mail_header ); // TRUE oder FALSE
Linuchs