This is a really interesting idea; I was thinking this morning that it would be nice to see something like this if we were so fortunate as to get a CoX 2. I think you raise some good points about potential pitfalls, but I also think that there are ways around them. Just as a thought experiment, how do you think this would work?
Essentially, mez protection, rather than being the on/off switch that it currently is, would act to decrease the effectiveness of status effects. At full effectiveness, you'd have something like this:
Hold = -100% recharge, -100% movement; Stun = -100% recharge, -80% movement; Immob = -100% movement.
But the total effectiveness would be scaled down by a factor MAG/PROTECTION. For example, Char is a MAG 3 hold with a base duration of 10 seconds (I think). If I recall correctly, the protection that scrappers get from their protection power ends up being 10. So if you hit a scrapper with Char, the hold would operate at an effectiveness of 3/10=30%. Instead of being completely incapacitated, or completely shrugging everything off, he'd suffer a debuff of -30% recharge, -30% movement until the hold wore off.
Now, if NPCS had a base protection of 2, 3, and 4 for minions, lieuts, and bosses (which I believe is the current system), a controller would still be able to one-shot mez a minion or a lieut, but would require two applications to incapacitate a boss. However, instead of being completely unaffected by a single MAG 3 hold, the boss would suffer -75% debuffs to recharge and movement. This would also open up a lot more options for AV fights.
This would probably require way too much rebalancing (and coding) to be anything but a pipe dream for CoH as it currently stands. But if I were going to make my own superhero game, I'd try something like this.