Email from PHP has broken Subject header encoding

Update For a more practical and up-to-date answer, have a look at Palec’s answer.

The specified character encoding in Content-Type does only describe the character encoding of the message body but not the header. You need to use the encoded-word syntax with either the quoted-printable encoding or the Base64 encoding:

encoded-word = "=?" charset "?" encoding "?" encoded-text "?="

You can use imap_8bit for the quoted-printable encoding and base64_encode for the Base64 encoding:

"Subject: =?UTF-8?B?".base64_encode($subject)."?="
"Subject: =?UTF-8?Q?".imap_8bit($subject)."?="

TL;DR

$preferences = ['input-charset' => 'UTF-8', 'output-charset' => 'UTF-8'];
$encoded_subject = iconv_mime_encode('Subject', $subject, $preferences);
$encoded_subject = substr($encoded_subject, strlen('Subject: '));
mail($to, $encoded_subject, $message, $headers);

mb_internal_encoding('UTF-8');
$encoded_subject = mb_encode_mimeheader($subject, 'UTF-8', 'B', "\r\n", strlen('Subject: '));
mail($to, $encoded_subject, $message, $headers);

Problem and solution

The Content-Type and Content-Transfer-Encoding headers apply only to the body of your message. For headers, there is a mechanism for specifying their encoding specified in RFC 2047.

You should encode your Subject via iconv_mime_encode(), which exists as of PHP 5:

$preferences = ["input-charset" => "UTF-8", "output-charset" => "UTF-8"];
$encoded_subject = iconv_mime_encode("Subject", $subject, $preferences);

^{Change input-charset to match the encoding of your string $subject. You should leave output-charset as UTF-8. Before PHP 5.4, use array() instead of [].}

Now $encoded_subject is (without trailing newline)

Subject: =?UTF-8?B?VmVyeSBsb25nIHRleHQgY29udGFpbmluZyBzcGVjaWFsIGM=?=
 =?UTF-8?B?aGFyYWN0ZXJzIGxpa2UgxJvFocSNxZnFvsO9w6HDrcOpPD4/PSsqIHA=?=
 =?UTF-8?B?cm9kdWNlcyBzZXZlcmFsIGVuY29kZWQtd29yZHMsIHNwYW5uaW5nIG0=?=
 =?UTF-8?B?dWx0aXBsZSBsaW5lcw==?=

for $subject containing:

Very long text containing special characters like ěščřžýáíé<>?=+* produces several encoded-words, spanning multiple lines

How does it work?

The iconv_mime_encode() function splits the text, encodes each piece separately into an <encoded-word> token and folds the whitespace between them. Encoded word is =?<charset>?<encoding>?<encoded-text>?= where:

<encoding> is either B (for Base 64 – see base64_encode()) or Q (for Quoted-printable – see quoted_printable_encode()),
<encoded-text> is string encoded with <encoding>, which has charset <charset> after being decoded.

You can decode =?CP1250?B?QWhvaiwgc3bsdGU=?= into UTF-8 string Ahoj, světe (Hello, world in Czech) via iconv("CP1250", "UTF-8", base64_decode("QWhvaiwgc3bsdGU=")) or directly via iconv_mime_decode("=?CP1250?B?QWhvaiwgc3bsdGU=?=", 0, "UTF-8").

Encoding into encoded words is more complicated, because the spec requires each encoded-word token to be at most 75 bytes long and each line containing any encoded-word token must be at most 76 bytes long (including blank at the start of a continuation line). Don’t implement the encoding yourself. All you really need to know is that iconv_mime_encode() respects the spec.

Interesting related reading is the Wikipedia article Unicode and email.

Alternatives

A rudimentary option is to use only a restricted set of characters. ASCII is guaranteed to work. ISO Latin 1 (ISO-8859-1), as user2250504 suggested, will probably work too, because it is often used as fallback when no encoding is specified. But those character sets are very small and you’ll probably be unable to encode all the characters you’ll want. Moreover, the RFCs say nothing about whether Latin 1 should work or not.

You can also use mb_encode_mimeheader(), as Paul Norman answered, but it’s easy to use it incorrectly.

You must use mb_internal_encoding() to set the mbstring functions’ internally used encoding. The mb_* functions expect input strings to be in this encoding. Beware: The second parameter of mb_encode_mimeheader() has nothing to do with the input string (despite what the manual says). It corresponds to the <charset> in the encoded word (see How does it work? above). The input string is recoded from the internal encoding to this one before being passed to the B or Q encoding.

Setting internal encoding might not be needed since PHP 5.6, because the underlying mbstring.internal_encoding configuration option had been deprecated in favor of the default_charset option, which has been set to UTF-8 by default, since. Note that this is just a default and it may be inappropriate to rely on defaults in your code.
You must include the header name and colon in the input string. The RFC imposes a strong limit on line length and it must hold for the first line, too! An alternative is to fiddle with the fifth parameter ($indent; last one as of September 2015), but this is even less convenient.
The implementation might have bugs. Even if used correctly, you might get broken output. At least this is what many comments on the manual page say. I have not managed to find any problem, but I know implementation of encoded words is tricky. If you find potential or actual bugs in mb_encode_mimeheader() or iconv_mime_encode(), please, let me know in the comments.

There is also at least one upside to using mb_encode_mimeheader(): it does not always encode all the header contents, which saves space and leaves the text human-readable. The encoding is required only for the non-ASCII parts. The output analogous to the iconv_mime_encode() example above is:

Subject: Very long text containing special characters like
 =?UTF-8?B?xJvFocSNxZnFvsO9w6HDrcOpPD4/PSsqIHByb2R1Y2VzIHNldmVyYWwgZW5j?=
 =?UTF-8?B?b2RlZC13b3Jkcywgc3Bhbm5pbmcgbXVsdGlwbGUgbGluZXM=?=

Usage example of mb_encode_mimeheader():

mb_internal_encoding('UTF-8');
$encoded_subject = mb_encode_mimeheader("Subject: $subject", 'UTF-8');
$encoded_subject = substr($encoded_subject, strlen('Subject: '));
mail($to, $encoded_subject, $message, $headers);

This is an alternative to the snippet in TL;DR on top of this post. Instead of just reserving the space for Subject: , it actually puts it there and then removes it in order to be able to use it with the mail()’s stupid interface.

If you like mbstring functions better than the iconv ones, you might want to use mb_send_mail(). It uses mail() internally, but encodes subject and body of the message automatically. Again, use with care.

Headers other than Subject need different treatment

Note that you must not assume that encoding the whole contents of a header is OK for all headers that may contain non-ASCII characters. E.g. From, To, Cc, Bcc and Reply-To may contain names for the addresses they contain, but only the names may be encoded, not the addresses. The reason is that <encoded-word> token may replace just <text>, <ctext> and <word> tokens, and only under certain circumstances (see §5 of RFC 2047).

Encoding of non-ASCII text in other headers is a related but different question. If you wish to know more about this topic, search. If you find no answer, ask another question and point me to it in the comments.

mb_encode_mimeheader() for UTF-8 strings can be useful here, e.g.

$subject = mb_encode_mimeheader($subjectText,"UTF-8");