В MySQL сущесвтует собственный поиск, в мане прочти о MATCH() AGAINST() вроде так. работает. Хотя тут можно и обойтись обычным LIKE с его % и ?. Создавать кеш на час... да, возможно это как вариант, только при добавлении нового номера задерка вывода будет примерно пол часа. В принципе это не критично. Насчет постраничного вывода, что может быть проще? Маленький запро SELECT COUNT() не сильно загрузит сервак. Зато будет очень удобно листать, например, по 50 номеров.