OK, we have lots of machines that we host out on slicehost. We want them to be part of our domain (foo.ourdomain.com). So, we configure their hostname to be that. Unfortunately, we want them to be able to send mail to people in our domain (firstname.lastname@example.org). Since the machine thinks it is part of the domain, it looks for that user, can't find them and consequently fails to send the mail out.
Testing sendmail, it always drops the mail into dead.letter immediately.
To fix this, I simply edited /etc/mail/sendmail.cf and uncommented the domain, setting it to some fictitious name (since the machine won't be the destination for any mail.
I uncommented this line: