Hay varias razones... la mas probable es que la ip de donde estes enviando el correo este en una black list (que son las listas de computadores conocidos que envian spam) por lo tanto tu mail no aparecera en gmail hasta que esa ip salga de la black list (cosa que pasa muy poco) o a menos que cambies el metodo de envio.
La otra razon podria deberse a que estas enviando mal las cabeceras.. por ejemplo si envio un mail en from sin nombre podria arrastrar a algunos correos como hotmail o yahoo a que me los envien a los no deseados... pero intenta completando al maximo las cabeceras... en varias paginas de san google sale mucha informacion... te dejo la mision de buscar: "mail headers php"
Suerte!
