Hola:
Tu validación no cancela el submit, así que si bien detecta los problemas, el formulario de todas formas se envía...
Las validaciones deberían declararse así:
<form onsubmit="return valida(this)"...
Lo del "this" es para referenciar al formulario y conseguir un código reutilizable (al menos con pocos retoques)
El "return" debe recibir false para cancelarse, así que deberías llevar un valor lógico o al menos controlar eso...
Por ejemplo así:
return (validaNombre && validaApe);
Te paso un tuto:
El abc de los formularios
Saludos