The unexpected part for me was not the lack of temporal locality, but which cache it thrashed. The whole dataset fits into buffer cache so one might think that the lack of locality is not that important...
I was going to use UUID with the time portion at the start (also known as UUIDv7) but this looks better.
I've been thinking about converting a legacy application which uses UUIDv4 to use ULIDs instead going forward, but then to represent these ULIDs in a format that is compliant with a UUIDv4. I have not thought through the possible downsides, but I think it should be a pretty straightforward change. Of course old records will remain true random UUIDv4s, but at least new records will be time-order and as such will create less stress on the B-Tree index when writing them.
One potential downside is ULID does not have an RFC, unlike UUID V7