Search without a setting configured should open the Settings dialog to the page which configures search. On that page should be a list of the current well know

Search without a setting configured should open the Settings dialog to the page which configures search. On that page should be a list of the current well known / trusted providers (this can be a cached copy for offline config), maybe a refresh button (check for an updated version of that list), and a method of providing an end user installed search option. In short: Empower the End User.