No, reread the parent's statement. The test involves distinguishing exactly one known accepted request and exactly one known rejected request. Probability of an acceptance does not come into play here; hence a random algorithm would choose the accepted request correctly 50% of the time.

What the algorithm performs poorly at is determining whether any single arbitrary request is accepted or rejected; that's the test that would require around 80% success rate.

Eh - ok - let me rephrase. anything below 0.8 with ROC curves is usually considered to be very poor.

Can't quite recall the paper that gives the details. Think it might be this one http://www.hpl.hp.com/techreports/2003/HPL-2003-4.pdf

From the PDF you cite:

"Since the AUC is a portion of the area of the unit square, its value will always be between 0 and 1.0. However, because random guessing produces the diagonal line between (0, 0) and (1, 1), which has an area of 0.5, no realistic classifier should have an AUC less than 0.5."

So it appears that not 0.8 but 0.5 is the randomness threshold; therefore 0.7 is not so bad.

Unfortunately not. IIRC, any classifier with AUC < 0.5 can be improved by just inverting its output. Real classification quality requires being significantly above 0.5 -- 0.8 is a common threshold.