Validando...

[autonotel]

bueno se me ocurre que le pongas el else:

function valida_envia(formulario){
//valido campos
if (formulario.nombre.value.length==0 || formulario.email.value.length==0 || formulario.pais.value.length==0 ||
formulario.fecha.value.length==0 || formulario.mensaje.value.length==0){
alert("Por favor, complete todos los campos.");
formulario.nombre.focus()
return false;
} else {
return true;
}}

y también que les pongas id a los input:
<input name="nombre" id="nombre"...


a ver si va