Effettivamente la soluzione è bruttina assai.
Invece di chiamare le checkbox col valore di $i, potresti trasformarle in un array in cui $i costituisce l'indice. Ad esempio name="elimina[$i]"

In questo modo nella pagina ricevente puoi fare un ciclo tipo

Codice PHP:
foreach($_POST['elimina'] as $key => $value) {
//in $key hai l'indice da eliminare
}