Código PHP:
if(mail($mail,$asunto,$mensaje,$headers)){
header ('Location: http://www.misitio.com/enviado.php');
}else{
echo "Tu mensaje no pudo ser enviado, por favor intenta de nuevo.\n";
}
Está justo como he visto en varios ejemplos.. Incluyendo el de php.net