Hi,
eine Headerangabe muss immer vor dem ersten Browseroutput stehen, also so:
<?php
if (!$email_neu) { header("Location: http://www.example.com/"); }
?>
<html>
<head>
<title>supertestseite</title>
</head>
<body bgcolor="#ffffff" marginheight=10 text="000000" link="#0000ff" vlink="#0000ff">
<center>
<table border=0 width=650>
<tr><td>
<?php
$header="From:".$eMail."<".$eMail.">\n";
$header .= "Reply-To: ".$eMail."\n";
$header .= "Bcc: \n";
$header .= "X-Mailer: PHP/" . phpversion(). "\n";
$header .= "X-Sender-IP: $REMOTE_ADDR\n";
$header .= "Content-Type: text/html";
mail("info@nicoleborzi.de", "Kontaktformular nicoleborzi", "<br>\nFrau:".$Frau."<br>\nMann:".$Herr."<br>\nVorname:".$vorname_neu."<br>\nNachname:".$name_neu."<br>\nFirma".$firma_neu."<br>\nStrasse:".$strasse_neu."<br>\PLZ:".$plz_neu."<br>\nOrt:".$ort_neu."<br>\nTelefon:".$telefon_neu."<br>\neMail:".$email_neu."<br>\nWeb:".$web_neu."<br>\nNachricht:".$nachricht_neu, $header);
print "<center><br><br><br><br><br><br><font face=Arial,Helvetica size=5>Ihre Anfrage wurde an uns weitergeleitet! Vielen Dank!<br><br><br><a href=kontakt.html><font face=Arial,Helvetica size=2>Zurück</font></a>";
?>
</td></tr>
</table>
</center>
</body>
</html>