Thanks for your comments.
>handing out xpubs makes the gap limit problem quadratic
Yes, my thinking on this is that if you're handing out xpubs you can lower the gap limit for addresses generated by those xpubs, provided you assume those addresses will be used by the same person, so there is less of a reason to expect a gap. This thread is related:
>How can we make a layer 1 address that expires
This was brought up by Sjors Provoost in relation to Silent Payments. He suggested embedding a sunset date in the address format.
>Could there be some more exotic deterministic path that doesn't split receive and change addresses
I don't follow this one. I see no reason not to split the two, and I do see potential pitfalls when you don't. Conceptually, I think receiving money twice on the same address is never good. Even if you're doing it to actively mislead people, that attempt is still leaking information that simply didn't need to be leaked.
Cheers,
Ruben