The message does show, but just for a second while the page submits. After submit the page is reloaded.
I think I answered the wrong question to begin with. You don't want to show a message after the page submits, you want to show a message after the page reloads and the submit is processed.
To do that add a url parameter to the form either in the redirect of the email or don't use a redirect and add it to the form action tag itself, so that after the submit the url becomes something like: contact.php?sent=1
Then you can use php code to add a message to the page when that url parameter is present like:
<?php
if (isset($_GET['sent'])) {
?>
show this message when sent.
<?php
}
?>
You can delete the old javascript code onsubmit that I gave you. That would be used if the submit page takes a while to process and you want a message during the submit, or if you were submitting to a hidden iframe.