Despite the large number of SOQL fragments that include "order by Id", my understanding is that "order by Id" does not guarantee that the records are returned in insertion order.
(Is it only after deletion/emptying that results in out of order IDs or are there other circumstances? Does anyone have insight into why the IDs are not in order?)
Also CreatedDate appears to to have a granularity of 1 second. So while "order by CreatedDate, Id" will work most of the time, if two records are created within the same second where one ID is being reused, again the order cannot be guaranteed.
Is there a solution that guarantees that records are returned in insertion order?
Note that this question has been edited after comments were made: it originally said that ids are reused.