I'm not a regular Safari user, so I'm not 100% if this is true. But if I recall Safari doesn't return search results alongside the "most frequented sites" in autocomplete.

Maybe pulling up likely searches from Google adds some time than the locally-stored list of frequented sites.

That said, I'm purely speculating here.