[chrishajer]

Sounds like a local DNS issue:

http://drupal.org/node/1155

Of course, Google knows more about it that I do too:

http://www.google.com/search?q=sendmail+%22stat%3DData+format+error%22