LordCrash, this is a problem that has already been solved many times in RPGs made by companies like Bioware, based on testing for companions. Even your example requires testing for companons present, so I'm not sure why you see this as hard.
On a basic level, you could just limit it to character/origin tags, because they're the only ones that should be companions anyway, and then you just refer to the tags.
In the rare cases where both Sebille and Red Prince have an interjection, you can give each response a priority and choose one. If somehow you end up with 2 Sebilles with equal priority then you just flip a coin.
They are already spending a lot of time actually writing the dialogue and putting it in the game. It's not much extra work to set a flag to indicate that a particular response is prioritised as an interjection.
It's a very quick and easy thing to check.
