Observando las cabeceras del mail recibido puedes obtener más información sobre el motivo por el cual el mail ha sido marcado como spam (falta saber si lo marca como spam el servidor que lo recibe, un antivirus de tu equipo...)
Puedes probar con la opción -f y añadir la dirección de mail a la configuración de sendmail, o probar enviando los mails mediante smtp.
http://www.php.net/manual/es/function.mail.php
¿Si lo envías a otra dirección de mail también lo recibes como spam?