hotmailや特定の企業に届かないとして、
gmailやyahooメールには届くんでしょうか？
自鯖だけに届くとかいう落ちではないですよね。
届かないというとき、バウンスメールは返っているのでしょうか。

OP25の関係のような気もするけど。

相手先固有の問題だとすると、80番を開けているサーバからはメールを受け取らないとか
そういう相手方のフィルターかもしれないですよ。

まぁ、mb_send_mailの問題じゃないから、板違いかもよ