Has something changed in sendmail configuration that would make this start to be a problem?
Just wondering because it seems that this is a problem a lot of people are having. I looked up a sendmail configuration and stumble across this page
http://www.linuxselfhelp.com/quick/sendmail.html
They suggest that many mail servers don't like the localhost.localdomain being in the message header.