"Almost easy" NP-complete problems Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs. 

In other words, there is an  $A\in$ P, such that $L\Delta A$ is vanishing, which means 
$$\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap \{0,1\}^n|}{2^n}=0.$$
It also means that on a uniform random input, the polytime algorithm for $A$ will give the correct answer for $L$ with probability approaching 1. Therefore, it makes sense to view $L$ almost easy.

Note that $L\Delta A$ does not have to be sparse. For example, if it has  $2^{n/2}$ $n$-bit strings, then it is still vanishing (at an exponential rate), since $2^{n/2}/2^n=2^{-n/2}$.

It is not hard to (artificially) construct NP-complete problems  that are  P-density-close, according to the above definition. For example, let $L$ be any NP-complete language, and define $L^2=\{xx\,|\, x\in L\}$. Then $L^2$ retains NP-completeness, but has at most $2^{n/2}$ $n$-bit yes-instances. Therefore, the trivial algorithm that answers "no" to every input, will correctly decide $L^2$ on almost all inputs; it will err only on a $\leq 1-2^{-n/2}$ fraction of $n$-bit inputs.

On the other hand, it would be very surprising if  all NP-complete problems are P-density-close. It would mean that, in a sense,  all NP-complete problems are almost easy. This motivates the question:


  Assuming P$\neq$NP, which are some  natural NP-complete problems that are not  P-density-close?
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.