Flash solves the "added overhead for random access" portion of the problem, but the overhead for any access at all is still remarkably high, particularly when compared to main memory.

Perhaps when we get more "flash connected to the main bus" options (there are a few commercial options which sit in PCI Express, AGP, and even DRAM slots), we can begin discounting the overhead more and more, but we're not there quite yet.

Well, supposedly, cache-oblivious algorithms exist to deal with this kind of thing - by grouping related data together regardless of exactly what cache-scale you are at.