Is there a natural restriction of VO logic which captures P or NP?
For information, VO is in fact really more powerful than what you state; it contains the entire analytical hierarchy (hence, also the entire arithmetical hierarchy). The result is not published, neither submitted to any place, but you can find it on my page, www.milchior.fr/ho.pdf section 7 page 47. 

In it I show how VO lets you express addition and multiplication on order variable; may be some idea in this paper can help you. In particular I gave an equivalent definition (I prove it is equivalent) and I think it is more easy to use. (I wanted to avoid the fact that, in their definition of VO $\forall i \forall X^i\forall j\exists Y^j (X^i=Y^j)$ is false while    $\forall i \forall X^i\forall i\exists Y^i (X^i=Y^i)$ is true; which means that $i$ was changed after $X$ was quantified; hence it is useless to add "$^i$" when one quantifies $X$.

One straightforward restriction would be to forbid to quantify the same variable twice. I am pretty sure that the restriction is the class ELEMENTARY. The idea is that, for every formula $\phi(i)$ with a free order variable $i$, there would be one number $k$ such that forall $i>k$ the value of $\phi(i)$ would not change; hence if we can find this $k$ (which is probably an elementary function of the size of the universe) we can avoid to really check every possible $\phi(i)$ when we want the value of $\forall i \phi(i)$ but restrict it to $\forall i &lt; k \phi(i)$.

Else, you can certainly restrain VO by restraining the maximal order accepted; but then you obtain a "higher order" language (HO), and this is probably not what you want.