Quadratic algorithms are useless because performance matters? That is a textbook false dichotomy. Performance obviously matters, but the time hierarchy theorems suggest that there is certainly legitimate computation that requires quadratic time. Max flow will need at least quadratic time.
There are lots of algorithms with very high time-compleity that are still usefull in practice. One nice example is the decision-algorithm for Presburger arithmetic which runs in O(2^2^n).