Just faced this issue today and here are some tips on troubleshooting.
My environment (RedHat 5.9 , sendmail-8.13.8-8.1.el5_7)
While trying to send mail from command line
mail -s "Subject" user@domain < textfile
and monitoring /var/log/maillog I could see that message was rejected with below error
dsn=5.6.0, stat=Data format error
Not a very user friendly error description, so I’ve decided to trace communication with tcpdump between sendmail running on the host from which I’m sending e-mail and relay.
To my surprise this error was coming due to relay not accepting domain name of my server
I had few other servers that were sending e-mails fine to the same relay host, but these servers were running postfix, so I could not compare configuration to sendmail.mc or sendmail.cf files.
Tracing postfix to relay host communication with tcpdump revealed what domain name relay was accepting.
My next step was to masquerade domain name coming from sendmail and make it look same as the one coming from postfix
Here are a few articles that talk exactly about this
So including these lines in my /etc/mail/sendmail.mc file
MASQUERADE_AS(`myshortdomain.com')dnl MASQUERADE_DOMAIN(my.very.long.domain.com)dnl FEATURE(`masquerade_entire_domain')dnl FEATURE(`masquerade_envelope')dnl
Generating new sendmail.cf
make -C /etc/mail
and restarting sendmail
service sendmail restart
Fixed the issue for me.