If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?
You need to decide whether you want to talk in terms of decision problems (dealing with classes like $\textrm{P}$ or $\textrm{NP}$) or with function problems  (dealing with classes like $\textrm{FP}$ or $\textrm{FNP}$).

If you choose to talk in terms of decision problems, then the decision problem is to decide, given $(m, n)$, whether it is true that $m = 2^n$. This problem can indeed be solved (and thus verified) in polynomial time.

If you choose to talk in terms of function problems, then the problem is given $n$, compute $2^n$. This cannot be done in polynomial time, even with non-determinism, but just because the output is exponentially big with respect to the input. Verification has nothing to do here.