>I agree it's not as efficient as it could be, but how big is this problem in practice? Expecting payments on more addresses doesn't seem like a huge overhead. Or are you talking about the hassle of having to support spending from all these address types?

My worry is that once the number of standard scripts becomes significant, wallets will have to watch all of them. This could create a performance hit eventually, though I don't know what that would be in practice. Maybe someone else can offer more insight. It's possible to mitigate that using a tighter gap limit. But we still have the problem of wallets not supporting certain scripts. For example, Bob's wallet may not support wrapped segwit but Alice could accidentally send funds there assuming Bob can spend them.

SP proposes to use Taproot-only (as we've been discussing elsewhere), but I still don't think it's the right solution to lock down the BIP to a single script type, for the sake of future proofing if nothing else. Having address type flags solves these issues at the expense having a couple of extra bytes.

That's correct. This can't take advantage of compact block filters. Doing so would require having a notification address again. The scanning scheme is lighter and a bit simpler to implement than the one proposed by SP but it still presumes a full node.

It even seems to me that Bob doesn't even have to publish his key on-chain unless he intends on sending funds. Only senders would have to do so, and pure recipients (if there would be any such entities) would just have to publish their codes off-chain (e.g. website donation address). The downside is that Alice now has to publish her pubkey on-chain, which creates a footprint. She's now a confirmed user of stealth addresses. She can mitigate that by publishing an ephemeral pubkey for each recipient, but this might spiral out of control fast if the standard gains wider acceptance.

>Note that this mechanism is not safe against miners, as they can pay themselves arbitrarily high fees with no downside.

Good point. Perhaps the solution is to require an OP_RETURN burn instead. I thought it's better to benefit the ecosystem by sending coins back to miners, but burning is also possible.