На всякий случай проверьте, проиндексировано ли поле с телефонами; если нет или index minimal, переставьте на all. Скорее всего, проиндексировано, конечно.
Оптимальный вариант — переделать как советует da0c, только фиксированной длины не надо и пробелами не надо добивать, в FM это бессмысленно. Я тут потестировал одну относительно несложную переделку, но она еще медленнее оказалась.
Если база на сервере и SQL не принципиален, можно через HTTP GET данные запрашивать; данные будут в XML, но при желании в версии до 11 включительно можно их прямо там через XSLT прогнать.