EDITO:
Varias cosas:
1 - El form está dentro del <table> entre el tag table y tr. Eso está mal.... debería estar fuera.
2 - Hay un tr sin cerrar (el primero).
3 - No tiene sentido utilizar el evento onclick en el botón submit llamando a valida_envia si después haces los mismo en el action del form, por eso te aparecen 2 veces los mensajes. Yo haría onsubmit="valida_envia(this);return false;" y borraría el evento onclick del input submit.
Saludos