Обычный ответ хостинга, переходите на более дорогой тариф. Не повезло с хостингом. Не сейчас, так в другой раз что-то найдут и заставят сменить тариф.
Стандарный поиск prestashop особо не напрягает сервер, он сделан под минимальные требования. Единственое, что может быть, это ошибка в коде. Но у вас он работает, часть индексирует. Больше похоже на то, что у вас маленькие лимиты на обращение к бд и работу скриптов. Нужно попробывать работу сайта на любом другом хостинге. Перенести на локальный, взять тестовый хостингиг, многие дают тестовый период.
