Non ti conviene usare "il PRIMO id libero", ma "il PROSSIMO id libero".
Questo ti risolve tutti i problemi:
1) per sapere quale e' il PROSSIMO id libero, basta che ti tieni un contatore incrementato ogni volta che lo usi
2) l'ordine degli ID coincide con l'ordine temporale. Se vuoi "futtizare" l'ordine temporale,
2.1) il valore dell'ID non ti interessa tanto ordini su con campo data
2.2) se vuoi evitare problemi legali, non risolvi comunque il problema.
Ricuperare gli ID non ti fa risparmiare sul numero massimo di ID utilizzabili. Supponendo che l'ID sia un intero a 32 bit (valore massimo maggiore di DUE MILIARDI), e ti serve un ID al secondo, li finirai nell'Aprile 2086 (duemila OTTANTASEI). Direi che sarai bello che morto e sepolto .