¿Pero si te redirecciona el header()?
Bueno, si así sucede entonces no tienes problemas de código.
Recuerda que PHP no es un servidor de correo, así que entonces lo único que hace la función mail() es pasar el correo hacía el servidor de correo local.
Así entonces la responsabilidad de si se envía o no el correo no es problema de PHP.
Te invito a buscar temas similares en el foro, hay bastantes soluciones reales.