Can an NP-hard problem be polynomial on average?
It would seem that the question has been answered at CSTheory.SE.

Summary: it is, indeed possible.

For example, the Max 2-CSP problem is NP hard with an $O(n)$ expected time algorithm.

This makes sense, I guess. Sometimes only a small subset of instances is needed to make a problem $NP$-hard, like SAT vs 3SAT. But you can expand the problem, and as long as it still contains the hard instances, it will be NP-hard, but the probability of success with a fast algorithm will be raised.