1. правильный. переделать алгоритм на быстрый. посмотрите на http://mnogosearch.org, индексация баз данных.
2. разбиваете базу на части (скажем, по буквам алфавита) и делаете поиск сначала по букве 'A', потом по 'Б', каждый раз делая $response:location[http://ваш.сервер/этот_скрипт.html?letter=Б] потом letter=В
там можно и прогресс бар нарисовать, и stop нажать в любой момент.
