どうしてもうまくメールが送信できない場合にはサーバーのphp.iniの設定による原因の可能性があります。

現状以下サーバーで同様の現象を確認しています。
※現在デフォルトで「mbstring.encoding_translation」が「ON」になっていることが確認されているサーバー。

・ファーストサーバ
・WebArena（suiteX） ※NTT系
・NTTビズリンク（BizLink）　※NTT系
・スマイルサーバー
・CPI レンタルサーバ（KDDIグループ） ※ここはさらにイレギュラーなため、ページ下部にまとめました。

※余計なお世話ですが、こういったイレギュラーなサーバーは借りないほうが無難でしょう。経験上その他の設定もイレギュラーであることがあるため苦労させられることが多いです。

メールフォームで以下いずれかの症状の場合には対処する必要があります。
※フォーム側のhtmlファイルの文字コードとmail.php側の文字コードは問題無いことが前提です。

1，確認画面で文字化け、または項目が表示されない

2，必須設定にしている項目が入力しても「○○が未選択です」と出る（本来テキストフィールドは「未入力です」と出ます）

この場合、フォーム側から送られるデータ（POSTデータ）の文字コードと受け取る側のPHPの文字コードが違うために起こっていることがあります。

具体的にはphp.iniの設定で

mbstring.encoding_translation　がon
mbstring.internal_encoding　がeuc-jp

となっている場合はたとえば文字コードがUTF-8のフォームからのPOSTデータが強制的にEUC-JPに変換されるために文字化け（実際には表示されない状況もある）が発生し、結果正常に送信できなくなります。

※本来php.iniのデフォルトは「OFF」です。（なぜあえてONに？しかもUTF-8以外て・・・）
※というか本プログラムに限らずWordPressやEC-CUBEなど、今やUTF-8が標準なので当然影響が出ると思います。
※PHPプログラム側では変更できません（ini_set不可）

結論としてはとにかく「mbstring.encoding_translation」を「OFF」にすればいいわけです。
またはmbstring.internal_encodingで設定してある文字コードで運用する。

サーバーの設定を確認する
まずはサーバーのphp.iniの設定を確認してください。
以下ファイルをダウンロードし、解凍しinfo.phpをサーバーのどこでも良いのでアップし、ブラウザでアクセスしてください。
これはphp.iniの設定を確認するためのファイルです。
※作業後は削除下さい。

info.phpダウンロード


一番上にはPHPのバージョンが表示されます。
例　PHP Version 5.2.16

1，「 mbstring.encoding_translation 」でページ内を検索して下さい。（Ctrl+Fでページ内を検索できます）
「On」になっていませんか？
本来これはデフォルトでは「OFF」ですが、稀にサーバーによってはなぜか「ON」になっていることがあります。
原因の根本はこれです。

2，「 mbstring.internal_encoding 」で検索して下さい。
SJIS、EUC-JP、UTF-8のいずれかになっているかと思います。

対処法

1，「 mbstring.internal_encoding 」で設定されている文字コードでフォーム、及びプログラムを運用する
「 mbstring.internal_encoding 」が「EUC-JP」になっている場合には「EUC-JP」でフォームを作成し、プログラム側もEUC-JPにすれば正常に送信できます。
※サイト内で複数の文字コードが混在していても基本的には問題ありません。
例　トップページ＝UTF-8、お問い合わせフォーム＝EUC-JP
これが最も手っ取り早いかもしれません。

2，mbstring.encoding_translationを「OFF」にする
「 mbstring.internal_encoding 」が「EUC-JP（またはSJIS）」の場合で、既存のサイトがUTF-8でかつフォームもUTF-8で運用したい場合にはphp.iniの設定を変更する必要があります。
※「 mbstring.internal_encoding 」が「UTF-8（またはSJIS）」でフォームはEUC-JPで運用したい場合も同様です。
やり方はサーバーにより異なりますが、主に3通りのやり方があります。

1，htaccessを対象ディレクトリに置いて設定変更する
（サーバーによっては不可。不可のサーバーの場合、ページが表示されないなどが起こります）

2，サーバー管理画面でphp.iniの設定を変更する

3，php.iniファイルを設置し、設定を上書きする

いっそサーバー会社に「php.iniの設定でmbstring.encoding_translation」を「OFF」にしたいのですが？と問い合わせてもいいかもしれません。
これぐらいは丁寧に教えてくれるでしょう。サーバーの対応（やる気）も分かります。
※大量の問い合わせが来ることでマニュアル充実や仕様変更してくれることも期待できます。

ファーストサーバの場合
https://www.php-factory.net/cms/detail.php?id=1

WebArena（suiteX）の場合（NTT）、NTTビズリンク（BizLink）
https://www.php-factory.net/cms/detail.php?id=5

スマイルサーバーの場合（htaccessが使えません）
ちょっと面倒ですが以下を参考にして下さい。
http://support.smileserver.ne.jp/manual/soft/wordpress/3.html

CPIレンタルサーバーの場合
CPIの場合にはかなり厄介で面倒ですが、以下を参考下さい。

まずはPHPを使うための設定（デフォルトではPHP動かないんかいｗ）
※追記　どうやらこの仕様は廃止になった可能性があります。デフォルトで動いていそうです。
http://acesr.doc.secure.ne.jp/tools/php/

PHPの設定を変更する（mbstring.encoding_translationをOFFにする）
http://acesr.doc.secure.ne.jp/tools/php/php01.html

CPIなど借りたことが無いので実際には試していませんが、
mbstring.encoding_translation = OFF
で良いかと思います。
またmbstring.internal_encodingも
mbstring.internal_encoding = utf-8
としてください。

※追記
やはりphp.iniファイルに以下2行を書いて、該当のディレクトリに設置すればOKでした。
（設置したディレクトリのみに反映されます）
mbstring.encoding_translation = OFF
mbstring.internal_encoding = utf-8