Per i checkbox ti conviene utilizzare un array:
codice:
<input type="checkbox" name="cancellami[]" value="1" /> Mess 1
<input type="checkbox" name="cancellami[]" value="2" /> Mess 2
<input type="checkbox" name="cancellami[]" value="3" /> Mess 3
<input type="checkbox" name="cancellami[]" value="4" /> Mess 4
....
E nella pagina action del form avrai l'elenco degli id da eliminare nell'array $_POST['cancellami'] (immaginando che il form sia con method="post")

Per la query puoi costruire una cosa del genere:
codice:
$id = implode(',', $_POST['cancellami']);
$sql = "DELETE FROM tabella WHERE id IN({$id})";