Sometimes vague or implicit assumptions can make it unclear whether an algorithm is asymptotically optimal. For example, a lower bound theorem might assume a particular abstract machine model, as in the case of comparison sorts, or a particular organization of memory. By violating these assumptions, a new algorithm could potentially asymptotically outperform the lower bound and the "asymptotically optimal" algorithms.
See also:
http://en.wikipedia.org/wiki/Abstract_machine
http://en.wikipedia.org/wiki/Random-access_stored-program_ma...
http://en.wikipedia.org/wiki/Cache-oblivious_model
etc.
As far as I know all asymptotic analysis has to be done using some abstract machine model.
Really, if you doubt that the RASP model is appropriate for modern architectures, you can test it (a typical exercise in an algorithms course) -- see if, as the input size grows, the timing follows the asymptotic analysis. That is basically what the article you linked to does, and the results are not all that surprising -- where things are linear time in theory, they are linear time in practice; where they are quadratic time in theory, they are quadratic time in practice. It is worth pointing out that in all but the last example, the list and vector operations had the same complexity (because of the linear search), so it was really a comparison between constant factors.
I think the issue here is that, in the past, with shallower cache hierarchies, models that assumed a constant cost per memory access would maybe be off by smallish factor (I don't know, maybe 50%).
However, now memory access is frequently the limiting factor for an algorithm, and there can easily be an order of magnitude in variation between the average memory access latency for different algorithms (i.e. cache-smart versus cache-dumb).
What makes matrix multiplication an exceptional case is that the constant factor on the best known algorithm is so large that we do not know how to build a computer with enough memory to store a problem large enough to overcome that constant. That is not the case with this analysis of linked lists; all one can say is that the data sets chosen in that particular article (possibly representative of the most common data sets) are not big enough. One can certainly store a large enough data set to overcome the advantages arrays have, and so the only real question is, "Is it possible that the inputs will be so large?"
Maybe the answer is truly, "No, that is unlikely." I am skeptical, though, as there are not many cases where such statements can be made. Even software written for embedded systems that target specific products is likely to be repurposed for new systems with different inputs. Even researchers, who write software for the particular datasets sitting on their hard drives, often re-use their code in future work. There are "border" cases, like integer multiplication, but typically libraries will just select the best algorithm for a given input size (e.g. for multiplication, you'll probably only see FFT methods applied above a particular threshold). Perhaps linked lists are now a "border" case, but all that would mean is that we need to use abstract "sequence" operations that dynamically choose particular implementations to use as their sizes change.