De todas formas, aunque te redireccione a gracias.php, no tiene porque haberse enviado, porque, en tu codigo:
Código PHP:
mail($recipient, $subject, $msg, $mailheaders);
header('location:gracias.php');
no compruebas en ningun momento el posible error de mail(). Para hacerlo, debería ser una cosa asi:
Código PHP:
if(mail($recipient, $subject, $msg, $mailheaders)){
header('location:gracias.php');
}else{
echo "Mensaje no enviado";
}
Ya que mail devuelve true o false dependiendo se lo ha podido enviar o no. Deberias empezar comprobando eso, que realmente mail() lo manda bien.