I updated the last section. I ended up taking 3 random battles. Screw it though, goodbye Desert Palace, good ridance.
Esto Gaza
-I take Choco to Esto Gaza. I could have walked, but I'm going to have to go back and forth from the shore to Esto Gaza a few times, this is faster.
-The first screen in Esto Gaza can be troublesome with a random battle, but not that often.
-After the initial dialogue, the party gets healed. I recently did the section below before going to Esto Gaza, not knowing the party is healed and status free before proceeding. Wish I had known that beforehand.
-I go to the right and buy several missable items: -8 Zorlin Shapes. I need one for Zidane plus one. Zorlin Shapes are also responsible for three synthesis items. For both the Masamune and the Sargatanas, I need one for Zidane plus one. Sargatanas are then used to make Thief Gloves. I need two for the thieves plus one. I can auction one Thief Gloves, so I only need to synthesize two, for a total of 8 Zorlin Shapes needed.
-2 Flame Sabers. One for Steiner plus one.
-2 Heavy Lances. One for Freya plus one.
-2 Scissors Fangs. One for Amarant plus one.
-2 Asura's Rods. One for Dagger plus one.
-2 Hamelins. One for Eiko plus one.
-2 Octogon Rods. One for Vivi plus one.
-5 Black Hood. 5 for the lightweights plus one. I just picked one up in the Desert Palace, this makes 6.
I also bought another N-Kai Armlet. Among other things, it has awesome evade, and Zidane can finally learn Bandit. I also pick up the Wind Edge in this room.
-I then exit the way I entered and take Choco back to the shore. I optimize and unequip Vivi (to the give him the Octogon Rod, it's faster this way) and unequip Quina of all but the Rebirth Ring. I then save.

Limit Gloves from the Living Dead
-I am going to try out a different strategy than what the guide says. I am going to use the Iifa Tree strategy. Quina's Limit Glove will kill a Red Dragon. If Quina is zombied, Quina won't take any exp. However, unlike with Stop, I will receive the spoils, and if Quina has Millionaire activated, I can rack up about 35000 gil from the Red Dragons (at least, maybe more). Unlike Vivi's Stop, Quina's Limit Glove will definately work. However, like with using Vivi's Stop, this is going to take some luck. I will need the ATB and enemy attack departments to be in my favor, as Quina has no way of being immune to wind damage right now.
-Before any of that though, Quina needs to get zombied, and optimally also be set up for Limit Glove. Fortuantely, on the shores of the Lost Continent one can encounter a Gigan Octopus or a Whale Zombie. Whale Zombies have a move called Zombie Powder, which inflicts Zombie on one character. So, a Whale Zombie can open with Zombie Powder on Quina, Quina can self-KO/revive at some point and Zidane can Flee. And yes, Auto-Life does work on a zombied character. I didn't know this until it happened by accident, which makes this process a bit easier.
-This is however harder than it sounds. Whale Zombies have 5 different moves, so there's only a 20% chance of it doing what I want. It then has to use it on the right character. I can give myself better odds by KOing Steiner and Vivi, but Whale Zombies are rather fast, so it's kind of difficut to get in the first two moves. And then there's all the resets because of a battle with a Gigan Octopus. And finally there are the resets from getting a random battle on the way back into Esto Gaza. This last one has now happened four times in a row. I'll give it one more chance, and if I can't get through I'm going to just save after the Whale Zombie battle and again before entering Mount Gulug. I don't want to do this since I'm already expending more time, but I have my sanity to think of.
-At long last it happened. I didn't even have to KO Vivi or Steiner, the Whale Zombie opened with Zombie Powder on Quina all by itself. Steiner KOed Quina, who auto-lifed, and Zidane used Flee. And almost more importantly, I made it through that first screen of Esto Gaza without another random battle, finally.
-I go to the moogle, Mogrika got a letter, which I accidentally read twice, and then I got a letter to deliver and saved. All under two minutes, I think that's good.

So with that expeneded time, I am only two minutes behind what I was before I left Oeilvert. So had I not gone with this whole zombied Quina thing, I actually wouldn't have lost any time despite the two extra random battles I took in the Desert Palace. Hopefully I'll make up for that in Mount Gulug, where the Red Dragon battles should all go rather quickly.