How are you sending the messages? Pipe to sendmail? Net::SMTP? Mail::Send?

What sort of platforms are involved?

What mail server are you talking to?

Where's the code that's failing?