Gizamaluke's Grotto was... easy. o_O In my third time, I've petrified the first pair of Type A, and the second pair, I petrified in my first try. Gizamaluke, with Limit Glove, was a pushover as well. (btw, Quina revived with 1 HP in my very first try XD).
You got very lucky. It took me a good 15-20 tries before I even saw a black mage get petrified once. It took me like two days to do that part. They just wouldn't get petrified at all!