A solution to this would be to not have the omnibar scan through the entire history when typing in it. Instead, if the history does become too big, it should only wade through frequently visited pages and pages visited in the past month (or whatever is the best tradeoff for speed).