Good to hear I'm not alone on this.
I don't think that's my Barbie deck you're thinking of, but I have equally useless cards popping up here and there... like Halfling rogue; not so good at finding treasures now ;)
Some further ideas I had are maybe having different types of changes, for example a simple cost/power rebalancing, change of function, change of keyword... A card costing one more recruit might not bother you, but if it's like what happened to Overpower, you'll definitely want to rethink picking this card.
Also, maybe you could specify that the deck highlights when cards are added to a certain keyword? For example, A Mage deck will want to consider any newly added Mage cards for addition. Could this potentially be added to any feature of the card as well? Like a new card that gives gems, a new Quick common card or a card with modes.