You're assuming that a system where bosses aren't immune to most status effects are going to have the exact same status ailments as the games we have today. Some status effects are just idiotic to begin with, and instant death is one of them. Not being immune to stop wouldn't let you breeze past them if it took you 20 turns to make it stick, and then it would wear off after 10 seconds. As I said earlier, it shouldn't be a one-bit system where you either are 100% vulnerable or 100% immune, but a gradual thing. Also, in some games, petrify doesn't permanently disable you anyway. They are just functionally similar to a stop spell instead, and wear off in time, or when you take damage.
When I say most status effects should be possible to use on all bosses, clearly I do not mean that this should be implemented without balancing the gameplay to take this into account, that's just ridiculous.
Also, Vanille's death ability was like that, Skyblade, and it was really smurfing idiotic. Things like that shouldn't exist in games because they don't do anything but frustrate players. It reduces a game of any complexity to simply rolling a 100-sided dice until you get a 100. It's boring and really stupid and whoever comes up with design like that should be dragged behind the barn and shot in the ear.
Random chance to instantly die is stupid in every game I see it in, no matter which side can use it. It's dumb when I can use it on enemies, and when enemies can use it on me.