Мы делали так, на странице, например, N=30 записей. Если результат выборки возвращал менее (N+0.5N)=45 записей, то показывали все первой-же странице, если результатов было больше 45, то разбивали на две страницы и тд... То есть если следующая страница результатов поиска заполнена менее чем наполовину, показывать эти результаты на текущей.
Я в таких случаях предпочитаю нажимать первую букву и автоматически попадать в нужное место отсортированного списка