I am experiencing the same issue with any version of 1.3, including 1.3.3. All orders are unsearchable by their ID with the exception of the first handful of pages. Rolling back to 1.2.12 fixed the issue.
I have about 9,000 orders.
I was prompted to update the database once when first upgrading to 1.3. Similarly to @marioprimal, I have not seen the DB update prompt since, even when rolling back and testing the 1.3.3 update. No errors in the error log when attempting the failed searches or plugin updates.
