デコードツール

検索してみたところ、Foundstone から DumpAutoComplete v0.7 というツールが提供されているようです。

DumpAutoComplete v0.7
Dump Firefox AutoComplete files into XML
http://www.foundstone.com/us/resources/proddesc/DumpAutoComplete.htm

ということで、早速試してみたのですが、残念ながら日本語文字列の部分は正常に抽出されてこないようです。ひょっとすると使い方を間違っている気がしないでもないですが、たぶんダメなんではないかと結果から勝手に思ってます。

Morkフォーマット？

よくわからんですが、formhistory.dat ファイルの先頭に mdb:mork と書いてあるので mork で検索してみたところ、そいうフォーマット？があるんですね。Perl から普通にデコードできるみたいですけど、これ文字コードは何使ってるんだろ...
参考URLのメモ

http://qootas.org/blog/archives/2006/02/firefox_history.html
http://d.hatena.ne.jp/sfujiwara/20060604/1149445141
http://d.hatena.ne.jp/sfujiwara/20060605/1149488462