N>Скажем двумя таблицами, или одной таблицей.. хоть как-то, лишь бы поиск по базе выполнить один раз, а не дважды.

1) загонять результаты поиска во временную таблицу — для больших резалтсетов выигрыш может быть отрицательным
2) убедить заказчика отказаться от счётчика записей. Просто читать первые 11 , показывать 10 и по наличию 11 показывать или нет кнопку "дальше"

я за 2й способ, хотя и понимаю, насколько священная корова этот счётчик записей