Por lo que comenta josemi . hice mi comentario sobre usar variables "de control" tipo:
Código PHP:
if ($tal=="tal"){
header("Location: pagina.php?var_control=1");
} else {
header("Location: pagina.php?var_control=2");
}
y en "pagina.php" (donde redireccionas) es donde debes gestionar tu var_control para presentar el mensaje de erro/exito que corresponda. (usando indices de arrays como el ejemplo va bastante bien ..)
Un saludo,