Problema con Formulario

[DanielDR]

Mira yo he trabajado un poco con esto y espero y esto te sirva

primero que nada en la parte del IF

if(isset($nombre) && !empty($nombre) &&
isset($mail) && !empty($mail) &&
isset($localidad) && !empty($localidad) &&
isset($telefono) && !empty($telefono) &&
isset($mensaje) && !empty($mensaje)) {
este es el tuyo ok

y yo lo pondria asi :

if(isset($nombre) && ($mail) && ($localidad) && ($telefono) && ($mensaje) !="" ){

creo que eso te falta y creo que debarias de quitar los !isset Asi como lo deje ok si no funciona avisame ok