I like where your head is, but spider and kraken are both locked. Only had one spider stone drop from chests so far anyway.
Searching full teams would help a LOT, but still wouldn't completely solve the problem. I've seen people throw in one super powerful toon with four unworked heroes,. But yes, the problem is that it's based purely on power rating. What they should do is either cap the rank of heroes you face within one level of your hishest ranked hero (mine are all purple +0, purple +1 is a challenge, purple +2 is brutal), team level within 5, maybe 10 for the last stage.
Another possible option is to rework power ratings so that it's more accurate, basically by making the curve more exponential. So, this Cutie being impossible to scratch by a team at 150% of its power rating should actually be rated at something more like 5-10x my team's power rating. That would have the bonus effect of making fully promoted heroes look even more badass, because who doesn't want more power? But it would also completely solve the problem of far-too-powerful heroes showing up in anyone's expo.