See #239825: drupal_mail(), CRLF, and Windows. The problem reported there applies to Drupal 6 as well.
Here's a repeat of the problem description:
E-mail uses CRLF for line endings. PHP's mail() API function is documented to require only LF endings in the message body. However, on Windows, mail() behaves differently and it is correct to give if CRLF; some MTAs (such as qmail) will refuse to accept messages from PHP on Windows if you only supply LF.
Comments