NTTが提供するWebArenaのsuiteXというプランではPHPのデフォルトの文字コードが強制的にUTF-8になっているため、フォームページ側の文字コードがUTF-8以外の文字コードの場合には文字化けが発生します。

当プログラムでの挙動は、必須設定したものが入力しても「○○が未選択です」と出ます。
これは必須設定に設定した文字と、フォーム側で受け取った文字が違うということを指します。
この場合、フォームで受け取った値が文字化けしたために発生します。

解決策

1，フォームhtmlファイル、及びメールフォームプログラムともUTF-8で運用する。
※サイト内で複数の文字コードが混在していても基本的には問題ありません。
これがもっとも手っ取り早いです。

2，htaccessでphp.iniの設定を変更する

フォーム側をどうしてもSHift-JIS、またはEUC-JPで運用したい場合には
以下記述を行ったhtaccessファイルをメールフォームと同じ階層（ディレクトリ）にアップします。
※以下はフォーム側がShift-JISの場合。EUC-JPの場合にはそのままEUC-JPと記述。

php_flag mbstring.encoding_translation off
php_value mbstring.internal_encoding SJIS

ただ実際には
php_flag mbstring.encoding_translation off

だけでもよかったです。

この場合、当然プログラムもShift-JIS版を使用してください。

以下ページにそれらしいことが書いています。
SuiteXに設置したメールフォームで送信したメールが文字化けをする。（SuiteX）
これはひどい・・・。なんとも無責任な文言ですがｗ

本来このあたりは重要なことなのでちゃんと解説すべきです。
ファーストサーバーでは少なくともちゃんと解説しています。
http://support.fsv.jp/manual/php/use/code.html

このあたりでもそのサーバーのやる気度が分かります。
※まぁそもそもこのようなサーバーは契約の選択肢には入りませんが。。

というかそもそもなんでデフォルトで指定しちゃうのかがまったく理解できません・・・。
なんかの嫌がらせでしょうか・・・。もちろん理由はあるんでしょうが、使う側のことを考えていないですね。
少なくともかなりの少数派です。
一般的なメジャーなレンタルサーバーではまずありません。