formulário com confirmação na própria página

pessoal,

gostaria de saber como fazer um formulário de modo que ao submeter os dados, a página atualize e apareçam os erros/confirmação de envio na mesma página, embaixo do formulário. não precisa ser ajax, nem nada desse tipo. acredito que alguém por aqui deva ter uma página/blog que utilize esse método, pq pelo que eu vejo por aí é muito comum.

eu só sei fazer de modo que depois do envio o usuário seja redirecionado a outra página, e do modo que eu faço é bem porco, pq eu teria que criar uma página pra cada erro. ;/

eu já tenho o formmail escrito por mim mesmo, adaptando de uns que eu encontrei na web e funciona perfeitamente. só não consigo gerenciar as mensagens de confirmação/erro. segue meu formmail, caso tenha alguma relevância:

<?

$nome = $_POST['nome'];
$email = $_POST['email'];
$mensagem = $_POST['mensagem'];

$de = "From: $nome <$email>";
$para = "Baunilha <victor.carcrash@gmail.com>";
$assunto = "Formulário euamobaunilha.com";

$corpo = "$nome
$email
$mensagem";

/ CLASSE PARA VALIDAR O E-MAIL /

Aqui tem uma classe enorme, pra validar o e-mail. Não é relevante.

/ FIM DA CLASSE /

AQUI COMEÇA A PORCALHADA. NÃO SEI O QUE FAZER.

if (strlen($nome) < 3) {
Header("Location: index.php?page=contato_404");
} elseif (strlen($mensagem) <= 3) {
Header("Location: index.php?page=contato_404");
} elseif (!check_email_address($email)) {
Header("Location: index.php?page=contato_404");
} else {

	mail($para, $assunto, $corpo, $de);
	Header("Location: index.php?page=contato_ok");
}
?>

Se alguém tiver apenas um link, já tá valendo. Não tô sabendo encontrar isso no google.

Obrigado desde já.