You should quoted-printable encode the subject header.
Like this:
$mail->Subject = "=?UTF-8?Q?" . quoted_printable_encode("The ï, ö, ë, ä, and é work, but when adding the ü it doesn't") . "?=";
Quoted printable encode in PHP: http://www.php.net/manual/en/function.quoted-printable-encode.php
Edit: $mail->CharSet = "UTF-8";
did the job.