This thread got revived just in time for my question. I'm stuck at this fight at the moment with a party of Terra, Celes, Locke, and Shadow. Between them I've got Fire, Ice, Bolt, Holy, Storm (that's Wind and Water, right?), but no one has Poison. Am I screwed here?
FYI I seem to have the opposite experience of Noonic-- I found the random encounters of Kefka's Tower so tough and resource-consuming that I had to grind up for a while and try it again. All my characters were level 30 when I first tried it.