Ich Idiot! Vor lauter Testerei habe ich übersehen, dass ich sämtliche POST-Variablem mit utf8_decode umgewandelt habe.
Mit folgendem Header funktioniert es jetzt:
$header = "From: $visitor_email\nContent-Type: text/plain; charset=ISO-8859-1\nContent-Transfer-Encoding: 8bit\nReply-To: $visitor_email\nX-Mailer: PHP/" . phpversion();
Danke für Eure Hilfe!