Error con mail()

[temerariomalaga]

Yo he ido siguiento todos los consejos que me han ido dando, porque si no nunca me funcionaria el envio del formulario. Puede que en algún momento me haya confundido y haya subido el código del notepad en vez del que tengo en la web.
El correo que me mandaste me ha llegado correctamente, pero ahora he copiado el código que pusiste y sigue sin llegarme unos cuantos formularios de prueba que me he mandado. Para que no haya dudas, el código de PHP que tengo en la web es:

Código PHP:

  <?php 
if(isset($_POST['enviar'])){ 
$Nombre = $_POST['nombre']; 
$Email = $_POST['email']; 
$Asunto = $_POST['asunto']; 
$Mensaje = $_POST['mensaje']; 
$header ="MIME-Version:1.0\nContent-type:text/html;charset=UTF-8\nFrom:".$_POST['email']."<br/>"; 
$mensaje = "Nombre: ".$Nombre."<br/>"; 
$mensaje .= "Email: ".$Email."<br/>"; 
$mensaje .= "Asunto: ".$Asunto ."<br/>"; 
$mensaje .= "Mensaje: ".$Mensaje."<br/>"; 
$mensaje .= "Enviado el " .date("d/m/y \a \l\a\s H:i:s "); 
$para = '[email protected]'; 
 
 
 if(mail($para,$Asunto, utf8_decode($mensaje), $header)){ 
     echo "Su mensaje se ha enviado correctamente"; 
 }else{ 
       
 } 
}   
?>   

y el código HTML del formulario es:

Código HTML:

<div id="formulario">
		<p>Puede contactar tambi&eacute;n rellenando el siguiente formulario con los datos solicitados.</p>
		<form name="formulario" action="" method="post" onsubmit="return validacion()">
			<label for="nombre">Nombre: </label><input type="text" size="50" value="" id="nombre" name="nombre" /><br />
			<label for="email">Email: </label><input type="text" size="50" value="" id="email" name="email" /><br />
			<label for="asunto">Asunto: </label><input type="text" size="50" id="asunto" name="asunto" /><br />
			<label for="mensaje">Mensaje:</label><textarea cols="37" rows="10" id="mensaje" name="asunto"></textarea><br />
			<input type="submit" name="enviar" value="Enviar" class="boton" />
		</form>
	</div> 

Muchas gracias por tu ayuda loncho_rojas y siento si ha parecido que no he usado tus consejos, pero los he usado uno por uno y no se como he podido volver al código del principio. Gracias de nuevo