Bueno, lo mas q tu puedes hacer es, revisar los headers del correo y agregar parametros q sean como el de un envio normal, puedes tambien utilizar una cuenta, para autentificarte y enviar los correos autentificados, esto da mas confianza de que no es SPAM, por ultimo puedes ver una clase llamada PHPMailer, muy sencilla.
http://phpmailer.sourceforge.net
Saludos.