SQLiteのfull-text indexing(全文索引)機能の導入に伴い、Firefoxも履歴やブックマークの全文検索をサポートするのはほぼ確実だと思います。

http://www.sqlite.org/cvstrac/wiki?p=FullTextIndex
https://bugzilla.mozilla.org/show_bug.cgi?id=342915

そこまではいいんですが、問題は日本語対応です。単語が空白で区切られている欧文と違って、日本語（に限りませんけど）では、わりと正確に分かち書きしないと、検索精度ががくっと落ちます。今、出回っている全文検索アプリケーションは、大抵、形態素解析ツール（フリーでは、KAKASI、ChaSen、MeCabなど）を使って、単語や形態素まで分離してから、改めてインデックス化しています。

性能をとるなら、MeCabあたりをバンドルするのが一番いいと思いますが、MeCabのわかち書き辞書だけで、圧縮しても5MBを軽く超えているんですよね。Firefoxには5Mルールというのがあって、Windows版のサイズを5MB以下に抑えよう、ということで今までやってきていますから、どうあがいたって、公式版にMeCabを入れるのはムリだと思います。オーナーにもドライバーにも受け入れられないでしょう。

次善の案としては、言語依存の公式拡張にする、ということになろうかと思います。これにしたって、限りなく理想的に近い状態で物事が推移した場合で、ってことですけどね。まあ、やる前から諦めるのもなんですから。

ただでさえ日本と先進諸外国とでは普及率に差があるのに、このままでは、ますます離れていくかもしれません。まあ、そのこと自体はどうでもいいとしても、その要因が技術的なことだっていうのは残念ですね。

精度に拘らなくても、LuceneのCJKアナライザやThunderbirdのスパムフィルタに使っているようなアルゴリズムを入れておけば、案外満足のいくのが出来上がるのかもしれませんが…。