Magimaster in FF6 is a complete dick. You have to have fought him before in order to win. There's no way to predict that it will do ultima, and no way to lower ultima's damage significantly.

Immunity to almost all status effects is also unfair. It makes a whole class of magic useless for the fights that matter. In some games, it makes an entire character class useless in certain fights. Thing is that debuffs are often way overpowered, which they need to be if people are gonna bother with using them in random encounters rather than just spamming attack. At the same time, that level of potency makes them dangerously overpowered against many bosses.

The obvious solution here, is of course to make bosses more resistant to the effects than random monsters. For example Blind, it lowers accuracy extremely much on random encounters. They go from hitting you 95% of the time to 5% of the time, an accuracy drop of 90%. A boss starting to miss you 19 out of 20 times is way overpowered, so why not just have it resist blind instead of being completely immune? Where a random encounter loses 90% of its hit rate, a boss could be losing 10-15%, going from a 100% hit rate to a 85-90% hit rate. You still can't rely on blind to make you win, but it's certainly going to give you a few lucky breaks, save some MP you'd spend on healing, and so on.

Same with slow. If Slow reduces speed to 50% of normal against a trash mob, why not make a boss retain 80% of its speed instead of making it immune? With this system, the debuff-class you liked to use in this game is starting to be useful with stacking and keeping up several debuffs. Now you have a boss that both misses 15% of its attacks, and attacks at 80% of its normal rate. That's definitely noticable when applied to a long fight, but not broken.

It could be implemented pretty easily, by making each status resistance more than a one-bit yes/no value. Give it a scale from 0-100, where 0 gives it no resistance to the status effect (meaning all hits land at 100% potency) and 100 makes them completely immune. 50 would give the status effect a 50% chance to not miss, and also cut the potency by half when it does land. Above 50%, it gets exponentially less worth it to use status debuffs, unless you have special equipment or class traits that give magic accuracy bonuses to spells. Perhaps a debuff specialist would get traits that boost debuff spell accuracy by up to 50 percentage points, making it still easy to have debuffs land on resistant bosses, even if the potency is cut? Remember that being poisoned can hurt a lot if the monster has extremely high hp. If a full potency poison deals 5% damage each turn to a normal enemy with 8000 hp, that's 400 damage per turn. However, a boss could resist poison to the point where it deals only 0.5% of max hp per turn, but the spell would still deal more damage due to the boss having a max hp of 100000.