Isso acontece porque tu retornas logo um false. logo, se a função manda logo um false para naquele momento.
function valida_form (){
preenchido=true;
if(document.getElementById("adicionanomeparagem").value == ""){
var div = document.getElementById("validacaonomeparagem");
div.innerText = "Não pode estar vazio!";
preenchido=false;
}
if (document.getElementById(validacaonomeparagem)!="")
{
document.getElementById("validacaonomeparagem").innerText = "";
}
if(document.getElementById("adicionalatitudeparagem").value == ""){
var div = document.getElementById("validacaolatitudeparagem");
div.innerText = "Não pode estar vazio!";
preenchido=false;
}
return preenchido;
}
Faz desta forma, onde dizes se é true ou false numa flag que só depois é retomada! Força nisso!