Cita: Crei entender que deves ponerlo inmediatamente despues de la consulta para evitar en lo posible ese cruze de datos con otra peticion que pueda estar realizando otro visitante, pero ahora supongo se refiere simplemente a ponerlo despues ya que devuelve el id de la ultima consulta de esa instancia de codigo que se esta ejecutando y no el ultimo id introducido en la tabla por cualquiera.
Técnicamente esa es la ida, pero siempre hay alguna solución, como usar transacciones, o realizar toda la operación en un procedimiento almacenado (que se ejecutan en la base y en una sola transacción). Las primeras evitan inserciones entremedio y las dejas en espera hasta que se libera todo, además de servir para asegurarse d que todo funcionó bien, y los datos se guardaron bien antes de confirmar todo.
Por otro lado, mysql_insert_id() opera sobre la conexión y recurso devuelto por la ejecución de la consulta de inserción, así que técnicamente debería ser independiente de las nuevas inserciones.
En cuanto a la tabla que mencionas, si el problema es que puede que llegue a millones de registos lo más importante en realidad nos son tanto los IDs que tenga, sino que esté correctamente definida y normalizada. En otras palabras, lo que debes modelar bien en ese caso es la base de datos, y no preocuparte tanto todavía por los IDs, que son asunto procedimental.
Empieza por optimizar la base. Para la aplicación siempre hay tiempo.