Purely in terms of UI, one possibility regarding maps and similar services, would be to allow the user to choose a preferred provider the first time (s)he searched for a location, like in the Windows browser choice dialog the EU forced Microsoft to implement.