This is actually answered in the sendmail FAQ at

http://www.sendmail.org/faq/section3.html#3.34

This sounds like it may be your issue.

Cheers,
KM