В принципе ничего сложного. Можно сделать базу структурой:
uin, 2002, 2003,2004, 2005 где в годах будет мыло :]
Если я смогу вытянуть эти базы (у меня модем), то попробую сделать.

сделай просто на тестовых базах.то есть создай наобуум несколько строк
типа :
234232:y_ne@dyra.com
888199:y8908@d890ra.com

Уже удалось кое-что сделать а именно:

• Я сгенирировал базу 100001-999999
• Для каждого уина есть емайлы за определённые года 2000 2003 2004 2005
• можно задавать маски * или ? (как http://icq.xss.ru/)
• Все запросы кешируются (при повторном запросе sql сервер не задейсвован)

Правда поиск по email я ещё не добавил, нужно придумать маску
Думаю допустимыми символами будут: a-z 0-9 _ - .
Вроде, если емайл не входит в эту маску, то он не может реально существовать (если я неправ - поправте!)
Все емайлы сгенирированны! Любой совпадение есть чудо!
Думаю завтра доделаю поиск по емайлам и начну добавлять базы. (нашёл только за 2003 год и то с левой кодировкой )
Вот такие пироги...
http://mailovka.ru/icq/

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

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

Не очень понимаю как это, я делаю обычный поиск типа:
(Это кеш страници, а не кеш запроса к БД)
Кеш работает в течении часа, потом странице пресобирается (Smarty рулит )

Вот это как-раз и проблемно:
Если делать постраничный вывод, то нам ведь всё-равно нужно как-то определить кол-во страниц? :] Тоесть запрос будет полноценный.
Можно сделать так:
Ограничить вывод в 100 уинов (LIMIT 0 , 101)
Добавить поле, которое задаёт значение "откуда начинать"
Например по запросу всего 500 уинов, нам надо узнать промежуток от 300-ого уина, тогда мы в это поле вводим 300 (запрос будет LIMIT 300, 101)

Теперь почему 101, если вывод 100.
101-ого уина не будет в выводе, но если у него есть значение, то значит есть и следущая страница :]

Этот структура рабочая но неправильная. Неправильная потому что когда появятся новые базы (2006 и 2007 годов) ты должен будешь модифицировать структуру БД (добавляя новые атрибуты 2006, 2007).
Лучше всего воспользоватся структурой вида:
uin, year, mail - где поля year и uin ключевые.
Сразу отпадает проблема поиска по мылу

Deem3n®: Да возможно это и не лучший вариант, дабы я не очень силён в SQL, но мой способ простой и понятный (для меня).
Да, когда будут появлятся новые базы за новый год, то это дело прийдётся немного править (добавить пару строк), но вся прелесть в том, что раз в год можно выделеть несколько минут на это
Если я тебя правельно понял, то хочешь хранить в базе уины так (напиши правельно понял, или нет):
uin year mail
667033 2001 vasya@mail.ru
667033 2002 peta@mail.ru
и тд

В принципе у меня скрипт готов. Осталось только придать дизайн и добавить кнопку "к следущей странице" (сегодня сделаю, но не успею выложить инет до 8) Ну и добавлять базы...
Поиск емайла может быть по маске и за определённый год (не забывайте ставить галочку "год" (можно поставить все) )
Ещё есть идея собрать все ники и uid юзеров форума у кого 6-ти знаки, тогда в дополнительном поле будет имя и ссылка на профиль (если администрация поддержит, то будет класно )
Тестируем! О багах постим сюда

http://mailovka.ru/icq

ну в принципе так, но для экономии сделай тип атрибута year - tinyint:
uin year mail
667033 99 fedya@mail.ru
667033 01 vasya@mail.ru
667033 02 peta@mail.ru

PS:
для чего предназначена опция "Вывод от:"?

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