Y ¿el número del ID está directamente relacionado con la antiguedad? Porque si no es así, puedes recorrer la tabla en busca de espacios vacios e ir agregando ahí, es costoso a nivel de optimización sobre todo cuando tienes muchos registros, pero, el problema está básicamente en que tengas que mostrarle al usuario el ID cuando ni siquiera ha hecho un registro efectivo, la idea de raul338 de una tabla alternativa y temporal tendría el mismo problema con espacios vacios.

¿Es 100% necesario mostrar el ID antes y no después del registro?