There's default settings, and then there's "default" settings. I think of Debian's debconf and how there are different levels of prompts when installing a package.

A good compromise would be to ask on use. The first time someone searches say "What service do you want to complete this with?" and have Yahoo/Yandex pre-selected. Then never ask again.

The never asking again is the key part. IE's setup dialog is a problem because it's either answer a bunch of annoying questions now or answer a bunch of annoying questions later. It should be a choice of setup now or don't bother me again (unless I activate the setup wizard myself).