Since you are using /usr/lib/sendmail, I assume you are using qmail. If you are, you might want to look at http://web.infoave.net/~dsill/lwq.html#DNS-problem

If your /var/log/syslog is reporting this error in each case:

deferral: CNAME_lookup_failed_temporarily._(#4.4.3)

Then you have the problem. This exists primarily with large email provider addresses such as hotmail.com and msn.com. More explinations in the URL above.