e' abbastanza semplice.

il link 'elimina' lo devi creare dinamicamente.

Quando estrai i messaggi farai ovviamente una select. In questa select devi avere cura di estrarre anche l'id. In questo modo puoi creare i link così

echo 'elimina';

In seguito, nella pagina delete.php recuperi l'id della riga che vuoi cancellare

DELETE FROM tabella WHERE id=$_GET[id]