NTRUEncrypt proof that there are plenty of keys

Yes. Let $x^n-1=r_0^{e_0}(x)r_1^{e_1}(x)\cdots r_k^{e_k}(x)\pmod p$ be the factorisation of the polynomial $x^n-1$ into irreducibles in $\mathbb F_p[x]$, then the polynomial $f(x)$ is invertible in $(\mathbb Z/p\mathbb Z[x])^\times/(x^n-1)$ if and only if $f(x)$ is not divisible by any of the $r_i(x)$ in $\mathbb F_p$. If $f(x)\mod p$ is selected uniformly at random from polynomials of degree at most $n-1$ in $\mathbb F_p$ (e.g. each coefficient lies in a residue class with probability $1/p$) then $r_i(x)|f(x)$ is a probability $p^{-\deg(r_i)}$ event and by coprimality these events are independent for distinct $r_i,r_j$. Thus the probability of invertability mod $p$ is $$\prod_{i=0}^k\left(1-\frac1{p^{\deg(r_i)}}\right).$$ Given the $p^n$ possible choices of $f(x)\mod p$, this still represents a large proportion of possible choices. The worst case is when $x^n-1$ factors into $n$ distinct linear factors (which would be a poor choice for NTRU). In which case we would still have a probability $(1-1/p)^n$ and at least $(p-1)^n$ invertible polynomials mod $p$.

A similar, independent probability can be calculated mod $q$.