How to query records by insertion order in SOQL?

You can create an autonumber field on the object and order by that autonumber. Autonumber fields are number incrementors behind the scenes so they are not reused like Ids.