There are four important things to do back here. First of all, before you leave Madra, make sure you've updated your save with GS1 data (preferably a fully-completed game). If you don't, you won't be able to get a useful item.
Anyway, inside the town you'll see a weird woman who will occasionally make remarks about her sister, Menardi. Uh oh. She does indeed mean who you think she means, but we'll come to her later. Enter the two-floor house south of her. The old couple here will talk a little about mushrooms. You've picked up the Healing Fungus from Gondowan Cliffs, so talk to the old man, and give it to him. The old couple will thank you, and you'll get Char, the Mars Djinni! Make sure you set it to Jenna, because now this fourth Mars Djinni will not only let you summon Meteor, but let Jenna use the Aura Psynergies, which are whole-party healing spells (these aren't as good as Wish however).
Now, you can fully explore Madra Catacombs. Head into the catacombs via the entrance down the ladder by the little girl (not the one outside the walls). Follow the path around to the left, and in the next area, climb down. The tablet to the left of the door is actually a switch, so use Reveal and push the hidden button to open the doors. Go left inside, and north to a puddle. Use Frost on it. Go northeast to the viney pillar and push it into its hole. Head down and around the wall to get a chest containing an Apple. Go right to the pillar, and Move it across. Go back to the vine pillar, climb it, and jump across to the top of the ruin walls. Head across and around the walls, to the ledge formed by the slumping earth. Follow the ledge around to the pillar you moved before.
Across here, use Lash on the rope. Drop down the first groove, hop across the frozen pillar and onto the top of the building, then head through the door. Inside go through the left door (you can't actually go anywhere else). Use Tremor in here to get the chest off the top of the bookcase. Head back out. Follow the ledge to the left all the way down and climb down the vines at the end to get a Mist Potion. Climb back up and use the groove to get back down to the floor of the ruins. Head north to the door below the one you just entered.
Inside, go through the double doors to the north. In this room, get the Ruin Key from the chest (this is the chest that was on the bookcase earlier). The stairs up to the right lead nowhere, as does the left door, so head through the right-hand door. Head north and up the stairs. Follow this path to get a Lucky Medal from a chest. Now head back and go down the stairs you passed in the familiar room.
The huge door down here can be opened with the Ruin Key. When the torches have lit up, head up to the combo tablet. You can now summon Moloch! He requires 2 Mercury and 1 Jupiter on standby. Now, Retreat from the ruins. You can use the Apple on whoever has the lowest Attack.
Use the Inn or Sanctum if you need to, then head to the mayor's house, up the stairs to the left of the weird woman. Head inside and approach the Mayor. After saying hello and telling them that everything's worked out all right, leave the building. If you were about to wonder if the Mayor was going to be as stingy as the Alhafran one about giving you rewards, then don't worry, because he'll follow you and give you the Cyclone Chip. Equip this on Sheba when you can, but you won't be able to right now because the lady at the bottom of the stairs will suddenly interject. The fact that she remembers the name Felix and you remember the name Menardi doesn't bode well.
It's quite funny how in the face of the danger you know is only a few steps away, Piers is politely standing at the back, completely oblivious. Anyway, Karst will soon run off to find Issac. You're on your own anyway, and Karst and her partner only turn out to be hindrances, so the offer of help is an empty one. Once you're done talking, equip the Cyclone Chip on Sheba. Now, you can try and leave.
Extra Battle: Bandits
First of all, if you didn't update your save with GS1 data (by whatever means), or for some reason it's not actually past Vault yet, then you can skip ahead to the next section of this guide because this battle won't occur.
When you try and leave, the three bandits that stole the Shaman's Rod from Ivan in the first game will come looking for Issac. They overheard you talking about him, and they want to give him the "reward" they had planned for him.
They're really easy to beat. First turn, use one attack Djinn unleash on the center Bandit to kill him. Second turn, you can either do the same with two attack Djinn on each Thief, or just use strong Psynergies. Once they're dead, they'll offer to make up for what they've done (and avoid jail) by giving you the Golden Boots. Make sure you pick them up (you can leave them behind on the world map). Equip them on whoever you like.
Once you're done, head back to East Indra Shore, south of Dehkan Plateau.