Dovresti dare alle checkbox dei nomi "progressivi" come check1, check2, check3 ecc dove 1,2,3 sono gli id dei record. A questo punto l'utente ne spunta qualcuno e invia il form. Lato server dovresti scorrere tutto il recordset così:

while not rs.eof
if Request.Form("check"&rs("id")) = "on" then rs.Delete
rs.Movenext
wend

in questo modo controlli sequenzialmente tutte le checkbox (se valgono "on" vuol dire che sono state spuntate).

Questo è un modo, ma ci sono anche altre vie, ad esempio potresti impostare una variabile javascript che contiene tutti gli id selezionati. Più o meno così:

spuntati = "1,4,5,7"

Se l'utente spunta la check9 aggiungerai un ,9

spuntati = "1,4,5,7,9"

poi passi questa variabile lato server e fai:

cn.Execute "DELETE * FROM messaggi WHERE id IN ("&spuntati&")"

questo è più performante perchè compi l'operazione desiderata senza aprire un recordset e senza scorrerlo tutto. E' una soluzione mirata ma che ti farà penare un pò di più con lo script lato client. Provale tutte e due... ciao