There is a conflict between an algorithm's performance and its learning speed. Restricting ourselves to low amounts of data means we get algorithms with lower maximum performance than we otherwise would. These are then claimed to be better than algorithms which need more data to generalize well.
But I agree with you in general. I suspect even LFW's creators might; I don't know if they expected the benchmark to still be tested on this many years after creation.
I've always felt that all benchmarks in vision should come with expiration dates, because eventually everyone starts implicitly overfitting to them.
Outside training data has a huge influence on algorithm accuracy. For example, since Facebook has access to bajillions of face images that they could use to train their classifier, and since they can't share those images with the rest of the community, it's unclear whether their excellent performance is because they have gobs of data or whether it's really a better algorithm. I bet that a simple algorithm like a naive SVM might do leagues better if we could train it on Facebook's (hidden!) dataset and test on LFW. It just isn't reproducible---a measuring stick is only meaningful if everyone uses the same measuring stick.
That's one of the big surprises behind deep learning these days: it's now feasible to do things like "train a big neural network on bunches of images" in a sensible time. It's an optimization thing as much as it is a machine learning thing, in my opinion.
(Note that this is separate from the "unrestricted" vs "restricted" issue)
We should wait until Erik Learned-Miller lists this on the LFW results page. He'll know how to interpret their results.
Briefly skimming through this paper, it appears that these numbers are not a fair comparison, as this paper uses the unrestricted protocol of LFW[1], whereas the other methods in the ROC curve shown in the paper are using the restricted protocol. As you might imagine, the latter is more restrictive -- specifically in terms of amount of training data allowed. And as I mentioned in my previous comment, training data is king in these kind of systems -- more is always better.
To go slightly out on a limb, I think more significant than the new theoretical model proposed in this paper is probably the use of lots of different types of datasets for training. (Significantly more data >> more complicated models, most of the time.) But I'd have to read the paper much more carefully to be sure about this.
[1] http://vis-www.cs.umass.edu/lfw/results.html