Quando fai la SELECT per recuperare il messaggio controlli il numero di righe trovate nel database.
Puoi usare la funzione mysql_num_row() subito dopo mysql_query(). Se essa ritorna 0 righe lo avvisi che il messaggio è stato cancellato.

Qui trovi la documentazione sulla funzione mysql_num_row(): http://www.php.net/manual/en/functio...l-num-rows.php