Rare Steal always fail?

TL;DR: Steal is absolutely fine and understood; this phenomenon occurs because of two factors. One is that people are not good at estimating probabilities. The other is that FFVI's RNG function is pretty bad.

Both are correct. Though I would go with the latter one more likely because there are plenty of FFVI formula that are just bad. Like Evasion vs Hit Rate.