Rare Steal always fail?

Lobo's Special Attack is damage+50%, so unless you changed this, Brachosaur cannot be immune to a simple damaging special. Another possibility to consider is level disparities. If your thief isn't at least level 28, they cannot Steal from a level 77 Brachosaur, because they will be at least 50 levels under the target's level. Furthermore, if your level is very close to level 28, it may be possible to Steal in theory, but not in practice, since the RNG function that FFVI uses is rather limited, and none of the 256 "RNG sequences" that can be called will successfully pass the 50% ThiefKnife steal, and then the ~1% chance of successfully stealing, and then the ~12.5% chance of targeting the rare slot all at once.