Are there NP-complete problems with polynomial expected time solutions? Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)?

If not, are there problems for which the existence of such an algorithm has been established?

Or does the existence of such an algorithm imply the existence of a deterministic polynomial time algorithm?
There is a polynomial time algorithm for finding Hamiltonian cycles on random graphs, that succeeds asymptotically with the same probability that a Hamiltonian cycle exists. Of course, this problem is NP-hard in the worst case. 

They also show that a dynamic programming algorithm which is always guaranteed to find a Hamiltonian cycle, if it exists, has polynomial expected running time, if the input distribution is uniformly random over the set of all $n$ vertex graphs.

Reference: "An algorithm for finding Hamilton cycles in random graphs"

Bollobas, Fenner, Frieze

http://portal.acm.org/citation.cfm?id=22145.22193