My sense is that there are hard 3-coloring problems in graphs that don't look "random". Certainly the ones I generate have a small number of vertices with very high degree, and the others are more reasonable. This is why I say that there are potentially things happening with different random models. But you are certainly right on all counts.

However, where you say this:

    .... it's been given "physicist proofs". There's enough
    evidence that it's unreasonable to not consider it true.

There had been a lot of evidence around for quite some time that primality was harder than P (assuming P!=NP), and yet it turns out to be in P, even without PvsNP being settled. I'm suspicious. I still believe that hard instances can be found, and that "most" of them will look as you describe, random-ish with the right parameters, but I'm wary about claiming that most things that look like that will, in turn, be "hard."

But I suspect we're in agreement, possibly "violent agreement."

ADDED In EDIT: Forgot to say, thanks for the reference.

Yes, we are in violent agreement then.

Easy to generate random hard instances does not at all mean that highly structured "non-random" instances can't be hard. The "phase transition" only means that the fraction that are hard at a given non-critical ratio decreases with n, but there very well could be a large absolute number, that increases with n. The space of problems of size n grows exponentially, after all.

My sense is that even before AKS, most researchers believed primality was in P. This was based mainly on poly-time probablistic algorithms developed in the 80's.