[Qz]

That depends whether, when you're talking about 'most applications', you mean most by sheer number, or most by processing time used. Because yes, there are a zillion tiny applications that don't care about VM space. But the ones that do are used far more often (running nonstop on servers, etc) than that random iBoobs app on your iPhone.

[slioslat]

Even for most applications "running non-stop on servers", VM is almost moot these days. For anything computational, swap is the kiss of death. For many applications where the working set is larger than available memory, the work is typically done inside a DBMS which usually has it's own systems for managing paging. Algos in DBMS are certainly aware of non-uniform access time: http://en.wikipedia.org/wiki/B-tree