They could give the choice to the user... When you boot up your phone for the first time, it would ask you to choose a default from a list of the 5-10 most popular search engines, sorted at random?