How is deciding a problem not equivalent to finding a valid certificate for verification?
The problem is in the following excerpt:


  iterate through the entire set of certificates


There might be many possible certificates. For example, a SAT instance on $n$ variables has $2^n$ certificates. Iterating through all of them would take exponential time. Although processing each takes only polynomial time, processing all would take exponential time. This is the difference between verification and decision.

Your argument does show that if a problem is in nondeterministic time $T(n)$, then it is in deterministic time $\exp T(n)$. For example, $\mathsf{NP} \subseteq \mathsf{EXP}$.