Is AUC the probability of correctly classifying a randomly selected instance from each class? I read this caption in a paper and have never seen AUC described in this way anywhere else. Is this true? Is there a proof or simple way to see this?

Fig. 2 shows the prediction accuracy of dichotomous variables expressed in terms of the area under the receiver-operating characteristic curve (AUC), which is equivalent to the probability of correctly classifying two randomly selected users one from each class (e.g., male and female).

It seems to me that it can't be true, since for AUC = 0.5, the above would suggest one has a 50% probability of correctly predicting a coin flip twice in a row, but in reality, you only have a 25% chance of correctly predicting two coin flips in a row. At least, that's how I'm thinking of this statement.
 A: The author's description isn't entirely accurate.  The area under the ROC curve is actually equal to the probability that a randomly selected positive example has a higher risk score than that of a randomly selected negative example.  This doesn't necessarily have anything to do with classification, it's just a measure of separation between score distributions.
For your coin example, imagine you have two coins and each has a score associated with it.  You then flip both coins until one comes up heads and the other tails (since we are conditioning on different outcomes).  This is equivalent to having a model that does random scoring, and the probability that the coin that came up heads has a higher (or lower) score is 1/2.
A: The description you have read is correct, though I dislike its wording. The area under the ROC (AUC) curve is the probability of correctly classifying a random pair of individuals into class 1 from class 2. It is a rank-based statistic, so if you had to guess whether one individual in pair is ranked higher than the other, that is only a 50% chance if guessing at random. The AUC is identical[1] to the Wilcoxon signed-rank test statistic, and this can be used to illustrate its meaning.
[1]: Mason & Graham (2002). Areas beneath the relative operating characteristics (ROC) and relative operating levels (ROL) curves: Statistical significance and interpretation. Quarterly Journal of the Royal Meteorological Society. 128: 2145–2166.
A: The quotation is slightly incorrect. The correct statement is that ROC AUC is the probability a randomly-chosen positive example is ranked more highly than a randomly-chosen negative example. This is due to the relationship between ROC AUC and the Wilcoxon test of ranks.
You will find the discussion in Tom Fawcett "An Introduction to ROC Analysis" illuminating.
A: As others pointed out, the AUC expresses the probability that a randomly chosen example from the positive class will receive, from the classifier, a higher score than a randomly chosen example from the negative class. 
For the proof of this property see:
How to derive a mathematical formula for AUC?
Or the source used for that answer:
D. Hand, 2009, Measuring classifier performance: a coherent alternative
to the area under the ROC curve
