Для отправки Unicode сообщений в PHP имеется функция mb_send_mail. Она доступна, если установлено расширение mbstring.
Если mbstring по умолчанию настроен, как нужно, проблем нет - но иногда бывает по-другому :-)
Чтобы не полагаться на .htaccess и прочие внешние факторы, настроить параметры отправки лучше прямо в коде:
mb_language("uni");
mb_internal_encoding("UTF-8");
mb_internal_encoding("UTF-8");
Таким образом, UTF-8 содержимое будет правильно интерпретировано mbstring.
Отправить письмо можно так:
ini_set('sendmail_from', $from);
mb_send_mail($to, $subject, $body, $from);
И $subject, и $body должны быть в UTF-8.
Предварительно можно перекодировать заголовки:
$from = 'From: "' . mb_encode_mimeheader('Петр Петрович') . '"
Ну, и пара линков по теме:
Unicode и PHP (julik live - на русском)
Что может неправильно работать в PHP при использовании UTF-8 (англ.)