Apresentar mensagem após envio de form e função header

Olá pessoal!

Bom o que pretendia era o seguinte.

Numa página existe um formulário, que envia para a mesma página, ou seja, o action do form é a página em que o form está, isto porque existe uma condição nessa página que só é executada quando o form é enviado. Isto porque essa condição apenas faz alterações na base de dados.

Mas eu pretendia que ao enviar o form, a página fosse actualizada, caso contrário, se o ustilizador actualizar por ele, irá aparecer a mensagem do browser, se pretende reenviar o formulário.

Mas o problema é que eu pretendo também que apareça uma mensgaem para o utilizador, sempre que envia o formulário. Neste momento tenho assim:

if (...) {
// instrução mysql

// header(location: page.php)

// mensagem informação
}

Mas neste caso, ao fazer o header, já não executa a mensagem, pois já não irá ler o "if".

Se trocar a ordem, primeiro a mensagem depois o header, a mensagem não chega a aparecer, pois o header executa de imediato.

Como posso fazer isso, após enviar formulário, aceder à página limpa de informação (sem rasto de formulário) e ainda apresentar uma mensagem (ex: form enviado)?

Obrigado pela vossa atenção, e peço desculpa pelo exagero no texto!