mb_encode_mimeheader()で文字列を変換する際は、事前にmb_internal_encoding()にてエンコードを統一しておかなければならない。

ということで以下のような処理が必要になる。

※メール送信クラスより引用

protected function mem($var) {
	// 関数の存在チェック
	$internalEncoding = function_exists('mb_internal_encoding');
	if($internalEncoding) {
		// 現在のエンコード設定を保存
		$restore = mb_internal_encoding();
		// 変換したい文字エンコードを設定
		mb_internal_encoding('UTF-8');
	}
	// 文字列を変換
	$return = mb_encode_mimeheader($var, 'UTF-8', 'B');
	// 処理後、変更していた文字コードを戻す
	if($internalEncoding) mb_internal_encoding($restore);
	// 値を返却
	return $return;
}

mb_encode_mimeheader()第3引数の’B’は「Base64」エンコードという意味。
‘Q’を指定すると「Quoted-Printable」になる。
デフォルトは’B’。

まぁ実際、関数の存在チェックまではやらなくてもいいと思う（適当）。