"Almost easy" NP-complete problems
I looked into whether there is a generally accepted hypothesis in complexity theory, which implies that there must exist an NP-complete language that cannot be accepted in polynomial time on almost all inputs (as defined in the question).

Interestingly, the most "standard" hypotheses do not seem to imply it. That is, it does not appear to follow (unless I overlooked something) from P$\neq$NP, P$=$BPP,
NP$\neq$coNP, E$\neq$NE, EXP$\neq$NEXP, NP$\neq$PSPACE,  NP$\neq$EXP, NP$\not\subseteq$P/poly, PH does not collapse,  etc.

On the other hand, I found one, slightly less standard, hypothesis, which does imply the existence of the sought NP-complete problem, albeit not a natural one.  In the theory of resource bounded measure the fundamental hypothesis is that NP does not have $p$-measure zero, denoted by 
$\mu_p($NP$)\neq 0$. Informally, this means that NP-languages within E do not form a negligible subset. For details, see a survey here. In this theory they prove, among many other things,  that 
$\mu_p($NP$)\neq 0$ implies the existence of a P-bi-immune language in NP. A language $L$ is P-bi-immune if  neither $L$ nor its complement has an infinite subset in P. Such a language satisfies our requirement in a strong way.

However, it still remains unclear whether an example exists that represents a natural problem.