So I don't recall what size of chunks Clojure's implementation uses, but I'll assume it uses 64-bit indices with 16-word chunks, because I want to use numbers.
(loop [i 0]
(println (get my-vector i))
(recur (inc i)))
Assuming no part of my-vector is cached at first, the first iteration needs to make a full 16 round trips to main memory — quite bad. But on the next iteration, all of that is cached, and we don't hit main memory at all, and the same until i=16, which requires one round trip. Then when i=16², we need to hit main memory twice, etc.
No doubt this is quite a bit worse than having everything nicely laid out sequentially in memory, but it's not as bad as you're describing.
Of course, all of that is not that material to begin with given that most elements will be pointers to begin with
I guess this is sort of true. If you're doing random lookups, then using a persistent vector instead of an array list mean 17 trips to main memory instead of just 1, so it's not totally inconsequential.
But I think (hope?) that modern JVMs can optimize collections of small immutable objects so that they're not represented as pointers to the heap. Surely ArrayList x gets represented as int x[], and not int *x[], at least with the most optimizing JIT level.