それは多分別の問題です

mb_send_mail($to, $subject, $message, $header)として、

$headerを$header = "from: hogehoge";って「from:」をつけて書かないと、

ヘッダー情報が本文にに含まれて送られちゃうという発見をしました。

$ php -r '
  mb_language( "ja"); 
  mb_internal_encoding( "UTF-8");
  mb_send_mail( "elf@elf.no-ip.org", "Subject", "Body", "X-Test: foo");'

で問題なく送信できます．
中のソースでもWindowsはFromを特別視していますが，Envelop From(第5引数)が指定されていないときにそれの値をでっち上げるためにFromを参照しているだけです．

おそらくヘッダーに使用している文字列の改行文字が複数種類混在しているのでしょう．

• Windowsのエディタで編集しているとCRLFになっていることが多い
• mb_encode_mimeheader()はデフォルトの改行はCRLF
• 第4引数でヘッダーを組み立てるときにLFだけで書くことが多い
• Windowsのメール処理(win32/mail.cだかだったかな)は改行コードを統一してから処理をするが，それ以外はそういう処理が入らない(そのままコマンドsendmailに渡っていく)

あたりが複数絡んでいて結果的にCRLFLFみたいなものができているだけなんじゃないでしょうか?

mail()でメールが送信できるかどうかの確認手順はmb_send_mailでも有効な話なので，調べてみるといいと思います．