I did some research and there doesn't seem to be an easy solution.
We can use the Scroll API, however it adds additional overhead and is, according to the docs, not designed for real-time user search.
We can use search_after, but it only works for sequential pages, not jumping to arbitrary pages. In the case of blocks, it could work because we can calculate the block number that a page will start on, but that doesn't work for transactions.
We can add a hard-limit to pagination to the UI (as suggested here) and recommend users to refine their search or sort. For example, instead of jumping to the last page of sort=blockno, you could go to the first page of sort=blockno:desc
This is an Elasticsearch limitation. A workaround would be to use a Scroll.
This problem appears on table views with a lot of entries, e.g. https://testnet.aergoscan.io/transactions