usare la mia prima query credo che sia la soluzione più veloce
magari invece del numero massimo di righe che può contenere una tabella MyISAM, usa come parametro il count delle righe della tabella (ovviamente, se usi MyISAM come Storage Engine, non ti porre neppure il problema XD )

se mancano le righe nel mezzo (traduco questa frase con "ho un elenco di id progressivi numerici non consecutivo") non ci dovrebbe essere alcun problema