１．fromの値が適切になっているか
自動で割り当てられたホスト名がFromに設定されていると、そんなアドレスは存在しないということでエラーになることがあります。
一番簡単な解決方法はMTAをsendmailからpostfixに変えて、設定ファイル（/etc/postfix/main.cf）でdomain名を変えてあげる方法です。
mydomain = ご自身のドメイン名
２．大量メール送信のリミット解除申請をしたか
AmazonではSpamメール送信を防ぐために、２５番ポートを利用したメール送信数に制限がかけられています。ローカルからメール送信をしている場合、これにひっかかることが多いです。
この制限を解除するためにはAmazonに解除申請を出す必要があります。
※ちなみに、解除申請にはElasticIPが必要です。設定していない人はEIPを取得し、ご利用中のインスタンスに紐づけてください。そしてEIPをご自身のドメインのAレコードに紐づけてください。
＜EC2メール送信制限の解除申請方法＞
下記のサイトに行きます。
https://aws.amazon.com/forms/ec2-email-limit-rdns-request
１．EIPを記入します。
Elastic IP Address 1 ＝ 取得したEIP
２．Reverse DNSを記入します。
Reverse DNS Record for EIP 1 = ドメイン名
３．第３者機関にスパム登録されていないか
/var/log/maillog を見ると下記のようなエラーが出ていることがあります。
＜IPアドレス＞ is listed on the Policy Block List (PBL).?? <http://www.spamhaus.org/query/ip/＜IPアドレス＞>
これはspamhous.orgという団体にスパムだと判断されたため、メール送付先ではじかれてしまっているということです。
上記のURLに行き、解除申請ができます。
申請しても特に確認メールは飛んできません。
３０分ほどで反映されるというメッセージがでますが、体感では１時間くらいかかった気がします。
４．mydestinationの設定は的確か
ローカルからメールを送信している場合、/etc/postfix/main.cfに設定されたmydomainと同じドメイン宛にメール送信できない場合があります。
その時は/etc/postfix/main.cfのmydestinationから$mydomainを削除します。