Обратите внимание на то, что функция php imap_search отправляет запрос поиска от клиента imap к почтовому серверу. Затем сервер принимает этот запрос и обрабатывает его на стороне сервера с помощью логики, специфичной для конкретного сервера imap. Поэтому, если вы не знаете внутренних деталей сервера imap, вы не знаете, как реализован поиск.
У вас вполне может быть один сервер imap, который будет эффективно выполнять поиск, в то время как другой сервер imap плохо его реализует. Так что с большими почтовыми ящиками у вас могут быть поиски, которые выполняются медленно и потребляют значительные ресурсы на сервере.
Я бы подумал, что единственной альтернативой, позволяющей избежать медленных поисков, было бы создание собственного менеджера почтовых ящиков, который синхронизируется с сервером imap и выполняет все локальные поиски с помощью эффективного алгоритма, который вы пишете для работы с выбранным вами хранилищем данных. Не простая задача.