Black Box Decision problem for NFA
Ellul, Krawetz, Shallit and Wang construct in their paper Regular Expressions: New Results and Open Problems a regular expression of length $n$ (for infinitely many $n$) such that the shortest string missing from its language has length $2^{\Omega(n)}$. Since a regular expression of  length $n$ can be converted to an NFA having $O(n)$ states, this gives, for infinitely many $n$, an NFA having $n$ states such that the shortest string not accepted by the NFA has length $2^{\Omega(n)}$.

Conversely, if an NFA having $n$ states doesn't accept all strings, then it must reject some string of length shorter than $2^n$. This follows from the pumping lemma once you convert the NFA to a DFA. Hence the construction in the paper mentioned above is optimal up to the constant in the exponent.