Do you have any way to confirm the sendmail configuration? Almost sounds like the sendmail server is denying some of your messages as relay attempts.

---

Zed? Zed's dead, baby, Zed's dead.