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'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.