I'm using Chrome 18.0.1025.11 beta-m, but I've had this problem since switching from Firefox over at least 5 releases.
I've found that history entries are often not reflected in the Omnibox when typing either document titles or URLs and the history search has the same behaviour. I can see the entries in the history, but they're not reflected in search results:
Edit: Embedded screenshot showing the problem. No matter how many times I visit the affected sites, they're never reflected in history search or the Omnibox. I don't think this is an Omnibox problem, but something more fundamental w/ history/search.
No matter how specific my search, the missing entries are never displayed. I rely on the browser history constantly for finding pages I've visited to avoid having to bookmark them, but there are dozens of pages affected and it's a real productivity killer.
I've already tried nuking the history completely (ie. uninstalling Chrome, removing all user data, reinstalling) with no luck.
Has anyone else had a similar experience?