da! Genau da! Da ist das Problem.
Lösung? Verwende nicht mail(), sondern eine Bibliothek wie z.B. den PHPMailer. Der weiß nämlich worauf es alles ankommt. Und der will auch Zugangsdaten zu einem SMTP-Server, damit er Mails so vesenden kann, wie Du es von einem Mailprogramm aus auch tust. Und GMX wird wegen des SMTP-Servers die Mail anders empfangen, als wenn sie von der mail()-Funktion kommt, weil GMX passend konfigurierten SMTP-Servern mehr vertraut, als irgendwelchen potenziellen Spam-Mail-Scripts.
Einspruch! Das kann die Lösung sein, muss es aber nicht. Auch hinter "mail()" kann eine saubere SMTP-Konfiguration liegen, ohne dass man davon überhaupt etwas weiß. Ohne den Grund der SPAM-Einstufung zu kennen, ist guter Rat schwierig.