After chatting with andytoshi and others, and some more thinking I've been convinced that my specific concern about other users masquerading other people pubkeys as their own in complex scripts is actually a non-issue.

No matter what you write in Script (today), you are limited to expressing some policy that is logically equivalent to a set of conditions and signatures on pubkeys that can be expressed in disjunctive normal form.  We can write such a policy as

(C[1] && PK[1,1] && ... && PK[1,m[1]]) || ... || (C[n] && PK[n,1] && ... && PK[n,m[n]])

where C[i] is some conjunction of conditions such as timelock constraints, or hash-lock constraints or any other kind of proof of publication, and where PK[i,j] is a requirement of a signature against a specific public key.

From Alice's point of view, she can divide set of clauses under the disjunction into those that contain a pubkey that she considers (partially) under her control and those clauses that she does not control (even though as we shall see those other keys might actually be under Alice's control, unbeknownst to her). To that end, let us consider a specific representative policy.

    (C[1] && APK[1]) || (C[2] && APK[2] && BPK[2]) || (C[3] && BPK[3])

where Alice considers herself in control of APK[1] and APK[2], and where she considers Bob in control of BPK[2] and BPK[3] and where C[1], C[2], and C[3] are different conditions, let's say three different hash-locks.  We will also say that Alice has ensured that her pubkeys in different clauses are different (i.e. APK[1] != APK[2]), but she doesn't make any such assumption for Bob's keys and neither will we.

When Alice funded this Script, or otherwise accepted it for consideration, she agreed that she wouldn't control the redemption of the UTXO as long as the preimage for C[3] is published.  In particular, Alice doesn't even need to fully decode the Script semantics for that clause beyond determining that it enforces the C[3] requirement that she cares about. Even if Bob was masquerading Alice's pubkey as his own (as in BPK[3] = APK[1] or BPK[3] = APK[2]), and he ends up copying her signature into that clause, Alice ends up with C[3] published as she originally accepted as a possibility.  Bob masquerading Alice's pubkey as his own only serves to hamper his own ability to sign for his clauses (I mean, Bob might be trying to convince some third party that Alice signed for something she didn't actually sign for, but such misrepresentations of the meaning of digital signatures is outside our scope and this just serves as a reminder not to be deceived by Bob's tricks here).

And the same argument holds for BPK[2].  Even if BPK[2] = APK[1] and Bob tries to copy Alice's signature into the C[2] condition, he still needs a countersignature with her APK[2], so Alice remains in control of that clause.  And if BPK[2] = APK[2] then Bob can only copy Alice's signature on the C[2] condition, but in that case she has already authorised that condition.  Again, Bob masquerading Alice's pubkey as his own only serves to hamper his own ability to sign for his clauses.

So what makes our potential issue here safe, versus the dangers that would happen in <https://bitcoin.stackexchange.com/a/85665/49364> where Bob masqurades Alice's UTXO as his own?  The key problem in the UTXO case isn't so much Bob masquerading Alice's pubkey as his own, as it is an issue with Alice reusing her pubkeys and Bob taking advantage of that.  We do, in fact, have exactly the same issue in Script.  If Alice were to reuse pubkeys such that APK[1] = APK[2], then Bob could take her signature for C[1] and transplant it to redeem under condition C[2].  We see that it is imperative that Alice ensures that she doesn't reuse pubkeys that she considers under her control for different conditions when she wants her signature to distinguish between them.

For various reasons, some historical, it is much harder to avoid pubkey reuse for different UTXOs than it is to avoid pubkey reuse within a single script.  We often use Bitcoin addresses in non-interactive ways, such as putting them on flyers or painting them on walls and such.  Without a standard for tweaking such pubkeys in a per-transaction way, we end up with a lot of pubkey reuse between various UTXOs.  However, within a Script, avoiding pubkey reuse ought to be easier.  Alice must communicate different pubkeys intended for different clauses, or if Bob is constructing a whole complex script on Alice's behalf, he may need to add CODESEPARATORs if tweaking Alice's pubkey isn't an option.

The conversion of a policy to disjunctive normal form can involve an exponential blowup (see <https://en.wikipedia.org/wiki/Disjunctive_normal_form#Conversion_to_DNF>).  For instance, if Alice's policy (not in disjunctive normal form) is of the form

    (C[1] || D[1]) && ... && (C[n] || D[n]) && APK

where C[i] and D[i] are all distinct hashlocks, we require O(2^n) clauses to put it in disjunctive normal form.  If Alice wants to create signatures that are restricted to a specific combination of C[i]'s and D[i]'s, she needs to use an exponential number of pubkeys, which isn't tractable to do in Script.  But neither my original proposal nor CODESEPARATOR helps in this case either because CODESEPARATOR can mark only the last executed position.  Taproot's MAST (Merklized Alternative Script Tree per aj's suggestion), can maybe provide a tractable solution to this in cases where it is applicable.  The MAST is always a disjunction and because the tapleaf is signed, it is safe to reuse pubkeys between alternative branches.

This analysis suggests that we should amend CODESEPARATORs behaviour to update an accumulator (presumably a running hash value), so that all executed CODESEPARATOR positions end up covered by the signature.  That would provide a solution to the above problem for those cases where taproot's MAST cannot be used.  I'm not sure if it is better to propose such an amendment to CODESEPARATOR's behaviour now, or to propose to soft-fork in such optional behaviour at a later time.

However, what I said above was even too simplified.  In general, a policy of the form.