Нужно сделать обязательно постраничный вывод, я думаю. Потому как наблюдать все сразу и неудобно и БД грузит, даже с кешами. Постранично, соответственно, лимитами делать. И вообще подумай над кешами ведь номера будут добавляться постоянно. поиск лучше юзать встроенный в MySQL, очень экономичный к ресурсам, тем более поля для поиска очень короткие. И начиная с 4-ой MySQL поиск там очень даже богатый вшитый, с кучей правил итп.

А вообще на самом то деле, задачи тут простейшие, можно было бы и на текстовиках сделать =)