En tu archivo de envio agrega la llave del registro al eliminar:
Código PHP:
...<input type="checkbox" name="registro[]" value="$row["llave"]" />...
Luego recuperas esa llave en tu archivo de eliminacion:
Código PHP:
$registro = $HTTP_POST_VARS['registro'];
foreach ($registro as $llave)
{
$query = "DELETE FROM tabla WHERE llave = ".$llave;
...
}