If you're hoping the instant providers list won't need to scale then you're essentially saying that we need a solution to the double spend problem. That is a good point. Double spends are one of the biggest issues remaining in the protocol. I've seen so many people talk about bad experiences trying to spend Bitcoin at a restaurant and waiting an hour for confirmations. This entire BIP extension is a band aid for double spends. If double spends are not resolved, there will be a million instant providers in the long run and if double spends are resolved then this BIP extension is completely unnecessary. Is solving doublespends off the table?
What if we solved doublespends like this: If a node receives 2 transactions that use the same input, they can put both of them into the new block as a proof of double spend, but the bitcoins are not sent to the outputs of either transactions. They are instead treated like a fee and given to the block solver node. This gives miners the needed incentive and tools to end doublespends instead of being forced to favor one transaction over the other.
I will write up a BIP if this seems like a practical approach.