This probably isn’t ready for primetime yet because it requires too much manual intervention but it’s a promising GreaseMonkey hack. MagicLine tracks where you’ve been, collecting loads of information like URLs, page titles, referrer, author, feeds and organizing it so that later, if you’re looking for something you’ve seen before, it can autocomplete based on any of this information.
Right now it modifies prefs.js with all this info and it will slow things down over time. Unless you really wanna play with this now, I’d squirrel it away for a future look-see … it sounds really promising.