Проблема тут ясна.. Это конструкция like '%чтотоздесь%', Приходится искать подстроки, которые находятся в середине поля, поэтому индексы практически не могут быть применены.

Посоветовать что-то радикальное тут сложно, но все-же:

- я бы посоветовал обновить mysql до версии 4. Первая цифра в номере версии была изменена в mysql, когда в нем очень основательно переписали внутренности, так что версия 4 масштабируется на большие обьемы данных значительно лучше..

- добавьте индексы, по одному на name и на address. mysql все равно будет вынужден перебирать записи по одной, однако такие индексы дадут возможность оптимизатору брать данные для перебора только из индексных файлов, не обращаясь к файлу данных. Это будет немного быстрее.. И соответсвенно надо раздуть параметр key_buffer в my.ini до размера, какой только возможен.. Скажем до 150M

- если поставите mysql 4, установите query_cache_size мегабайт в 20..30. Это позводит ускорить выборку в некоторых частных случаях, если скажем 2 человека ищут одну и ту же фирму (или если человек ищет ее несколько раз)


Все это были полумеры, и честно говоря они могут дать только непринципиальнй эффект. Вот несколько более коренных вещей, которые можно рассмотреть:

- посмотрите fulltext search . Может быть подойет.

- посмотрите, нет ли возможности изменить like '%blahblahblah%' на 'blahblahblah%'.. То есть организовать быстрый поиск по _началу_ названия (и скажем отдельной кнопкой медленный поиск в таком виде как он есть сейчас).. Констпукция like 'blah%' очень даже легко использует индексы (которые конечно надо все равно создать)