ご質問にある下記のコードでは正しい形式のメッセージは送れないと思います。
$subject = "タイトル";
$body = "本文";
$to = "mail@example.com";
$headers = "From: AAA株式会社<webmail@example.co.jp>";
$headers .= "\r\n";
mb_send_mail($to, $subject, $body, $headers);
まず、今どきUTF-8に対応していない (ISO-2022-JPしか読めない) MUAのことは考えなくていいでしょう。とりあえず当回答ではメッセージに使う文字コードはUTF-8決め打ちとします。また、以下にも述べますがmb_send_mail() にパラメータを放り込んだだけでは正しいメッセージになりませんのでmb_send_mail()は使わないほうがいいと思います。mail()を使います。
全てのコードを記載していませんので、抜けている部分は補ってください (動作確認していませんので、間違いがあれば指摘ください)。
ヘッダフィールド
例えば、上掲のコードだとFromヘッダフィールドの値が エンコードされた文字列@ドメイン名
のようになってしまっているはずです。フィールド値がまとめてエンコードされて一語になってしまい、MTAがドメイン名を補完したのだと考えられます (全体としてメールアドレスの形式にはなるので送信者ドメイン認証などは通ると思われる)。From、To、Ccなどのフィールドは構造化ヘッダフィールドなので値全体をまとめてエンコードしてはいけません。エンコードが必要な要素はエンコードし、他の要素と組み合わせてフィールド値とします。まじめにやるとこんな感じです (これでも問題が起きることはあるので後で若干手直しするかもしれません)。
$display_name = "AAA株式会社";
$address = "webmail@example.co.jp";
if (preg_match('/[^\x20-\x7E]/', $display_name)) {
$encoded = mb_encode_mimeheader($display_name, "UTF-8", "B");
} elseif (preg_match('/["\\]/', $display_name)) {
$encoded = '"' . preg_replace('/(["\\])/', '\\\1', $display_name) . '"';
} else {
$encoded = '"' . $display_name . '"';
}
$from_field = sprintf("%s <%s>", $encoded, $address);
Subjectについては全体をmb_encode_mimeheader()でエンコードすればいいと思います。
本文
mb_send_mail()ではmb_language()の値に基づいて適当に文字コード変換するので混乱の元です。今回はUTF-8決め打ちとしますので変換はしません。
本文については、今回はシングルパートでプレインテキストなので、8ビットのまま扱うか、適当な伝送エンコーディングをします。BASE64で伝送エンコーディングする場合、
$encoded_body = base64_encode($body);
メッセージの組み立て
各々の要素のエンコードができたら、メッセージを組み立てて送信します。MIME準拠のヘッダーフィールドも全部自分で指定します。
$headers = implode("\r\n", [
"From: " . $from_field,
"MIME-Version: 1.0",
"Content-Type: text/plain; Charset=UTF-8",
"Content-Transfer-Encoding: BASE64"
]);
mail($to_field, $subject_field, $encoded_body, $headers);
ひとまずこれで、通常なら正しく表示されるメッセージが送信できたはずです。これでも特定のMUAで文字化けなどがあるということでしたら、どんな状況なのかを改めて質問に追記ください。