Оказывается внутри Firefox2 и Fiorefox3 жестко зашит таймаут в 0,5 секунды на получение ответа от поискового сервера при составлении списка подсказок поискового плагина. По истечении этого интервала подсказка строится только на основе локальной истории запросов.
Однако, при желании этот таймаут можно увеличить, если найти на диске файл nsSearchSuggestions.js и увеличить в нем значение переменной _suggestionTimeout с 500 миллисекунд до 1500 или любого нужного вам значения, затем перестартовать Firefox.
Для FreeBSD нужный файлик лежит в /usr/local/lib/firefox/components/, для Ubuntu - в /usr/lib/firefox-3.0.5/components/