Si no quieres usar AJAX, que es lo actual y de moda, y que personalmente todavía encuentro difícil de domar (más que nada porque se escapa de la programación web clásica), puedes hacer la verificación en un simple iframe que sea invisible o bien de dimensiones 0 x 0 pixels.
Cuando presiones el botón de Envío de tu form, lo que harás será realmente cargar dentro del iframe un script php que recibirá los valores del formulario y los validará según lo que tú necesites.
Si está correcto, desde ese mismo iframe recargarás la página/marco padre con la dirección del script que procesa los datos finales del formulario y que muestra mensaje de "Correcto y Procesado"; de lo contrario, si la validación falla, puedes hacer saltar un mensaje Javascript (un alert() ) con un clásico "Datos incorrectos" o lo que quieras, y el proceso termina allí, sin que se recargue tu página principal.
Código HTML:
<!-- El iframe no debe verse -->
<iframe name="iframeValidar" width="0" height="0"></iframe>
<!-- El form -->
<form name="f" action="validar.php" target="iframeValidar" method="post">
Contenido del formulario
<input type="submit" value="Enviar">
</form>