Now it's been over a year since I played FF9, so I'll just make a few guesses:
Where are you at in the game? I don't remember if any weapons were elemental-attack based, but if you're in an area where random battles contain the same element, that might be why. =\ Again, that's probably not right, I don't remember what the weapons of FF9 were, I havn't played it in over a year. >>; I love the game though, I should replay it soon. After I finish Xenosaga2 and Star Ocean.
It might be the type of enemies you're fighting have an extreme amount of more defense than others. I doubt this possibility as well, but you can look up on it.
If you're levelled up, and the weapons arn't the problems, it's probably a glitch. I've never heard about anyone else having this problem though.