There is no such recursive ordinal, because in fact every computable ordinal is the order type of a polynomial time computable relation on $\mathbb{N}$. In other words, the least ordinal not describable by a polynomial time relation on $\mathbb{N}$ is $\omega_1^{ck}$, the same as the least ordinal not describable by any computable relation on $\mathbb{N}$, of any computable complexity.
To see this, suppose that $\alpha$ is any computable ordinal. This means that it is the order type of a computable relation $\triangle$ on $\mathbb{N}$. We may assume without loss of generality that $\omega^2\leq\alpha$, since the ordinals up to $\omega^2$ are clearly polynomial time describable. Let us now describe a new relation on a subset of $\mathbb{N}\times\mathbb{N}$, by replacing each $n\in\mathbb{N}$ with the pair $(n,k_n)$, where $k_n$ is a number describing in a very concrete way in its representation the complete relation of $\triangle$ on all numbers up to an including $n$ in the usual $\mathbb{N}$ order, plus the computations witnessing those relations. Note that we may easily recognize such pairs $(n,k_n)$ in linear time, since the very representation of $k_n$ reveals whether it is correct or not. We now define $(n,k_n)\lt(m,k_m)$ just in case $n\triangle m$. This is polynomial time computable from the input, because one of the $n$ or $m$ must be larger in the usual order of $\mathbb{N}$, and so the corresponding $k_n$ or $k_m$ exhibits the necessary information about $n\triangle m$. Finally, we extend our new relation to a total ordering of $\mathbb{N}\times\mathbb{N}$ by placing all other pairs $(n,k)$ not of the desired form as an $\omega$-sequence at the bottom of the order. This does not affect the overall order type of the order, since $\omega+\omega^2=\omega^2$ and consequently $\omega+\alpha=\alpha$. So our new relation is a polynomial time decidable relation on $\mathbb{N}\times\mathbb{N}$ of order type $\alpha$.
We may now easily convert the relation on $\mathbb{N}\times\mathbb{N}$ to a relation on $\mathbb{N}$, by means of the standard polynomial pairing function. Thus, we obtain $\alpha$ as a polynomial time describable ordinal, and so the conclusion is that complexity considerations do not affect the class of computable ordinals.
