Add/Remove effects only remove "player tokens". These are the ones placed on a character to control them.
The black token won't be discarded by such effect. The only character that can affect it is Melissa the Trobadour.
You're more than welcome!
Should more questions come up, I will be more than happy to answer them for you!
Thanks. It would probably have been clearer to call them "influence markers" so that the term "token" wasn't ambiguous.