As a motivating use case, Bitcoin Wallet for Android currently has a hard-coded block explorer (biteasy.com) which it uses to find UTXOs for a given key. This is used for its "Sweep paper wallet" feature. It must work this way because P2P nodes don't calculate such indexes.

If there was a way to do block index autodiscovery, that'd help us remove this hard-coded block explorer and increase decentralisation. But because it's a GUI app we don't want users to look at a spinner for more than a few seconds, so a slow discovery process would make it unworkable. With API-based categories of service bits we could implement such a scheme.