How longer you use firefox how slower the automatic search will be. There is a plugin thats defragment the search database.
Quote Vacuum Places Improved 1:
Defragments your Firefox “Places” database (history/bookmarks) This greatly reduces the lag while typing in the address bar and the start-up time. This extension features configurable automatic cleaning, periodic reminder, and internationalization.