High probable polynomial time algorithm for NP-hard problems?
Fernandez de la Vega and Karpinski in their paper 9/8-approximation algorithm for 
random max-3sat give, as the title suggests, such an algorithm under the uniform distribution over 3sat clauses. Håstad showed that no deterministic 7/8 approximation algorithms exists for max-3sat (unless ...)

I don't know of any clear-cut decision problems, i.e. ones where the algorithm beats an inapproximability result for an optimization problem.