申し訳ありません、追記させてください。
今使わせて頂いてるサーバさんの注意書きに

「CGIやPHPからメールを配信する場合にうまく送信できない場合がございます。
メール送信には、qmail付属のsendmail互換の送信プログラムを使用しております。
使用できるsendmailの引数は、(-t -f -bp -bs)です。
その他のオプションは使えません。」

このような事が書いてあります。
確かにkentさんのpostmailでは上手く送信できておりません。
上記の条件下でも上手く送信できるようなものをお願いいたします。