Ricordati che header, quando lanciato, non vuole assolutamente che sia stato stampato alcun output.
Tu però vuoi stampare un messaggio di cortesia..... quindi....
o usi OB_START() e funzioni relative per bufferizzare l'output HTML della tua pagina, da inviare in un secondo momento (cioè dopo che l'header è stato inviato), oppure usi un redirect in javascript con un timeout per permettere la lettura del messaggio di cortesia!
Oppure, non lanci alcun messaggio di cortesia.