Comment by gabrielgoh

A simple example of this that has been shown rigorously is compressed sensing. Finding the sparsest vector, subject to linear constraints Ax = b is NP hard for general matrices, but is solvable in polynomial time if A satisfies the RIP property (e.g. w.h.p if A is generated by randomly sampling gaussians for each entry). Quite surprising!