もう何回もPHPのメールはやってるのですが、
どうもサーバによってうまくいかなかったりします。
おそらく、ヘッダ作成がうまくいってないんでしょうね。
改造しました。
本来ヘッダのパラメータ区切り文字はCRLFだそうですが、LFでやってあります。
パラメータ間のスペースを削除してLFにするとうまくいく事がありました。
サーバーの仕様によってちがうみたいで、ややこしいです。

class Sendmail{
	
	/*
	$option=array(
			"to"=>test@test.com, 
			"subject"=>"タイトル",
			"body"=>"本文",
			"from_name"=>"送信者",
			"from_email"=>"form@test.com"
	);
	*/
	
	function __construct($option){
		$this->encoding="utf-8";
		$this->encoding_upper=strtoupper($this->encoding); 
		//print $this->encoding_upper;
		mb_language("ja");
		mb_internal_encoding($this->encoding);
		$this->option=$option;
	}
	
	function mimeHeader($str){
		//print "mimeHeader";
		return mb_encode_mimeheader(mb_convert_encoding($str,"ISO-2022-JP",$this->encoding_upper));
		
	}
	
	function send(){
		extract($this->option);
		$f_from_name=$this->mimeHeader($from_name);
		$headers= "MIME-Version: 1.0\nFrom: {$f_from_name}<{$from_email}>\nContent-Type: text/plain;charset=ISO-2022-JP \n";
		if($reply=="true") $headers .= "Reply-To: {$f_from_name} <{$from_email}> \n ";
		
		$subject =$this->mimeHeader($subject);
		$body = mb_convert_encoding($body, "ISO-2022-JP",$this->encoding_upper);
		
		$sendmail_params  = "-f$from_email";
		$result = mail($to, $subject, $body, $headers, $sendmail_params);
		return $result;
	}
	
}