Después de usar header() no puedes imprimir nada porque se pierde, así que eso debes imprimirlo en la pagina a la que haces la redirección.
Podrías pasar una valor en la URL para que se entienda la intención:
En tu otro script tendrás que verificar si dicho valor viene en la URL y entonces imprimir el mensaje apropiado.