If there is always a hard input for the complement of bounded halting, can that input be constructed?

More precisely, suppose that

for any deterministic TM $M$ accepting $$ \text{coBHP}=\{\langle N,x,1^t\rangle\mid \text{ nondeterministic TM N does not halt on input x within t steps}\}, $$ there exists some non-halting $\langle N',x'\rangle$ such that the function $f(t)=T_M(N',x',1^t)$ is not bounded by any polynomial.

In that case, given $M$, can $\langle N',x'\rangle$ be constructed by a polynomial time deterministic TM?

For background, see http://eccc.hpi-web.de/report/2009/056/