PHP sent emails have =0A=0A instead of new lines

For some time now I've had the problem of some of my users getting =0A=0A instead of new lines in emails I send to them via PHP. Correspondence via email client works well, but PHP generated emails always look like this with some users (a minority). Googling revealed no decent results, all search results seem to be connected with outlook somehow - and it is unacceptable to think that all outlook users would suffer from this problem. Does anyone know a correct way of handling this and avoiding these new line encoding issues?

Edit: FYI I'm using Zend's Mailer class.

Thanks

Edit 2:

Changing the encoding type did not work. I encoded the headers to base64, and the body to 64, got garbled stuff. Then I tried with base64 headers, and did base64_decode(base64_decode($body)开发者_JS百科) on the body, and that was fine on the user's "CNR Server but not in the inbox" whatever that means. When I tried mb_convert_encoding to base64, I got the encoded string instead of the body again, so no use.

What else can I try? Zend Mailer only supports Quoted Printable and Base64 header encoding. Not sure what to do to the body for it to match the quoted printable encoding...

The email body has been encoded using quoted-printable - but the mime type declared in the email is text/html (or text/plain or undefined).

How you make the encoding of the body of the email match the mime header is up to you.