> This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size.

You don't even need to go that far.

n^8 is smaller than 2^n once you get past 44, still well in the tractable range, but encrypting something against n^8 brute force is a pretty reasonable task.