Let two Hamiltonians $H_{1}$ and $H_{2}$ be defined in such a manner that their eigenvalue staircases satisfy
$ N_{1} (E) = N_{2} (E)+A +O(E^{-1})$
What can we say about their potentials $ V_{1} (x) $ and $ V_{2} (x)$ ?? Are they the same at least for $ x \rightarrow \infty$ ??
If we consider that the energy function $ E^i_{n}=f^i(n) $ as the inverse of $ N(E) $, will the energies be the same $ E_{n}^{1}=E_{n}^{2}$ in the limit $ n \rightarrow \infty$ ??
1) In this answer, we present a simple counterexample that provides negative conclusions to OP's questions (v2).
2) Consider the quantum harmonic oscillator
$$H~=~\frac{p^2}{2m} + V(x), \qquad V(x)~=~\frac{m\omega^2x^2}{2}+V_0, $$
with an additional zero-point energy $V_0$. The exact energy-levels are
$$E_n~=~\hbar\omega(n+\frac{1}{2})+V_0, \qquad n~\in~\mathbb{N}_0. $$
In particular, the full zero-point energy reads $E_0=\frac{\hbar\omega}{2}+V_0$. And
$$N(E)~=~ \frac{E-V_0}{\hbar\omega}-\frac{1}{2}.$$
3) Now consider two such quantum harmonic oscillators $H^{(1)}$ and $H^{(2)}$ with different zero-point energy
$$ \Delta V_0 ~=~V^{(2)}_0- V^{(1)}_0~\neq~0.$$
Then one potential $V^{(1)}$ is shifted everywhere with a constant relative to the other potential $V^{(2)}$,
$$\Delta V~=~V^{(2)}- V^{(1)}~=~\Delta V_0 ~\neq~0. $$
Similarly, the energy-levels are shifted
$$\Delta E_n~=~E_n^{(2)}- E_n^{(1)}~=~\Delta V_0 ~\neq~0.$$
but the difference
$$\Delta N(E)~=~N^{(2)}(E)- N^{(1)}(E)~=~ -\frac{\Delta V_0}{\hbar\omega}~=~\text{const.}$$
is of the type requested in the question (v2).
Consider the following case: $V_1$ and $V_2$ are confined inside the interval $[0,L]$ (i.e. are infinite outside it) and are arbitrary but bounded below some energy $E_0$ there. Then for energies $E$ far above $E_0$, the WKB approximation will hold for the quantization condition, giving $$\int_0^L\sqrt{\frac{2m}{\hbar^2}}\sqrt{E-V(x)}\textrm{d}x=n\pi+\textrm{const}.$$ Thus, the spectral staircases will satisfy the $O(E^{-1})$ identity you ask about. I would interpret this as saying that your identity says that your potentials look the same in some kind of classical limit (in this case, the particle is whizzing by so fast it doesn't notice the difference much) but the actual functions could be quite different.
