sendmailでは送信元は hostname や hostname -f あたりを拾ってきて使ってるようですが、 サーバーのホスト名とメールで使うドメイン名が一致するケースは少ないです。 そのため設定で書き換える必要があります。
sendmail-8.14の場合は以下
vim /etc/mail/submit.mc
---
define(`confDOMAIN_NAME',`{domain}')dnl
---
m4 /etc/mail/submit.mc > /etc/mail/submit.cf
service sendmail restart
追記
Sender address rejected: Domain not found
一部のメールサーバーに対してこんなログが出ていて、 ctladdr部分に解決できないドメインが指定されていると出てくる。
シェルからおこなう場合は submit.cf の変更でctladdrは変わり問題でなくなるけど、 PHPやPerlからのシステムメールの場合は submit.cf の方を通らないケースがあるもよう。
sendmail.cf の方も変更しておいた方が無難みたい
vim /etc/mail/sendmail.mc
---
define(`confDOMAIN_NAME',`{domain}')dnl
---
m4 /etc/mail/sendmail.mc > /etc/mail/sendmail.cf
service sendmail restart
