come diceva sky, devi effettuare una query condizionata con l'id, ad esempio

Codice PHP:
select id from tabella where id id_passato 
ed utilizzi la funzione mysql_num_row() per controllare se effettivamente quel record è stato eliminato o meno

Se essa ritorna 0 righe lo avvisi che il messaggio è stato cancellato.