In this survey of the P = NP problem, the author states on page 14 that the language $L$:
$$L = \{(<M>,x,0^s,0^t) : \exists w \in {0,1}^s \text{ such that } M(x,w) \text{ accepts in } \leq t \text{ steps}\}$$
is NP-complete, where $<M>$ is a description of the Turing Machine $M$. As far as I understand it, for a language to be NP-complete, it has to be such that if I have another NP language $L'$, then if I have some method of quickly verifying whether some element $\alpha \in L$, then I can quickly verify if an element $\beta \in L'$. (where quickly is used in the sense of polynomial time with respect to the input). And an NP-language $L'$ is defined to be one such that there exists a turing machine $M'$ such that given any $\beta$, there exists a $w'$ of polynomial length with respect to $\beta$ such that $M(\beta,w')$ will return in polynomial time whether or not $\beta \in L'$.
I can't exactly see why $L$ is NP-complete though. At first I thought the idea was that, given some NP language $L'$ and some element $\beta$, if we want to check whether $\beta \in L'$ then we can query:
$$ (<M'>,\beta,0,0) \in L?$$ $$ (<M'>,\beta,00,00) \in L?$$ $$ (<M'>,\beta,000,000) \in L?$$
and so on. If $\beta \in L'$, then seems to terminate in polynomial time, and we will be done. However, what if $\beta$ is not in $L'$? This process will never terminate (we will never be sure whether $\beta$ is in $L'$ or not). If the process never terminates though, then $L$ can't be NP-complete, so I think I'm doing something wrong.
As you say, the "certificate," $w'$ is required to be of polynomial length in the size of $\beta$. $L'$ is all and only those strings which possess such a certificate (I think your definition of NP may be a bit muddled). So you only have to check up to that polynomial.