Castle of Ordeal
The Castle of Ordeal is a mercifully short dungeon, but it is confusing and features several enemies that pose a significant challenge. There are three floors here, but the first features no encounters. The trip likely took longer than the journey to the treasure box containing the TAIL will. Don't use that as an excuse to let your guard down, though. Once you step onto the throne in the northwest room of the first floor, there is no way to escape the Castle except to fight your way to the end of it.
Castle of Ordeal 2F
The second floor is a maze consisting of white pillars that will teleport you from location to location. If you don't pay attention (or have a guide), you could end up wandering lost on this floor for some time. You don't want to do this, because there are a variety of nasty encounters waiting for you here.
The staple encounter is with ZomBULLS, big meaty monsters that aren't worth writing home about. They are Undead, but it's not worth wasting spells on them. The only noteworthy fact about groups of ZomBULLS is that you can't run from them.
R.GOYLES make their return from the Gurgu Volcano here, and in even larger packs. Your FIGHTER should resist Fire by this point, but they can still do a number on your mages. LIT3 can be effective, since they resist both Cold and Fire. SORCERERS also return, and powerful spells will help against them as well. ICE3 is a particularly good choice since it's not very useful against anything else in here.
The most dangerous new monsters here are MANCATS, which appear in packs but are thankfully uncommon on this floor. Similar to R.GOYLES, they usually open a fight with FIR2, and they don't have any weaknesses you can exploit. They resist every element, but you should be able to bully them physically. The problem is that their second spell is SLOW, which can cause serious problems for those physical attacks. The only good news is that after their third spell, DARK, they will fire off a sequence of weak spells you can ignore. You may want to run to conserve resources, but if you do fight, AFIR will go a long way in blunting their attack.
MEDUSAS aren't as dangerous as they appear. They have a pathetic 68 HP, and whole groups can be easily taken out with any multi-target attack spell. Their attacks are weak but Poisonous, but the real threat comes from their GLANCE ability, which can turn Warriors to Stone. It's not very accurate, and it's nothing a few SOFT Potions can't take care of. WzMUMMIES, who appear with large groups of MUMMY minions, are a similar story. The minions are no real threat and can be taken out with HRM2 or FIR2. The WzMUMMY is a bit tougher to kill, but its offense isn't particularly impressive.
Finally, you may rarely find yourself facing a ZombieD or two, the same encounter that serves as the boss of this dungeon! If you do, follow the same strategy as for that boss.
Teleporter Puzzle
To proceed through the teleporter puzzle, take the southern pillar at each of the first two forks, the eastern teleporter at the third fork, and the southernmost of the three in the eastern hallway.
Keep an eye out for the northeastern room. Inside you'll find a treasure box guarded by MudGOLS. These things like to cast FAST on each other, and their enhanced attacks are somewhat dangerous. They are simple enough to take out, though. To protect your more vulnerable Warriors, concentrate on any MudGOLS affected by FAST first. Your prize for winning this battle is the awesome Zeus Gauntlet. You can't actually equip it until the Class Change, and even then it's a middling piece of armor—but when used as an item in combat, it casts LIT2 for free! Give this to one of your mages and replace their basic attack with this ability to increase their offense substantially. Also note that if you really want to, you can skip this chest and find the Zeus Gauntlet in an unguarded chest on the third floor. Alternately, you can just run from the MudGOLS.
Castle of Ordeal 3F
This floor consists of four hallways connecting corner rooms. The encounters are basically the same as on 2F, but with more MANCATS and no ZomBULLS.
You'll run into a set encounter with some NITEMARES when you enter the door at the end of the first hallway. They wouldn't present much danger if not for their high Evade. To make matters worse, their SNORTING ability can cause Darkness. If physical attacks aren't cutting it, ICE2 can soften them up nicely, and ICE3 will likely kill them right out.
Make sure to collect the chest in this room, because in it you will find the Heal Staff, a useful weapon that casts HEAL for free when used as an item in combat. You will have to fight the NITEMARES again unless you edge around the square just inside the door on your way west.
The second tower contains more fantastic treasure. The Gold Bracelet is a great upgrade for any non-FIGHTER who doesn't have one already. The Ice Sword is useful if you have a RedMAGE or a second FIGHTER, or if you haven't found the first Ice Sword in Gurgu Volcano yet. The third chest contains an Iron Gauntlet, which can be sold or dropped depending on how much space you have for more loot.
A third tower contains yet more treasure, though the pickings are leaner. There is 8,795 G and a HOUSE here, as well as the alternate location for the Zeus Gauntlet. Once you've collected these treasures, you're in the home stretch. The final room contains a chest and a throne. You'll find the TAIL you came for in the chest, but before you can step on the throne to teleport out, you will be faced with one or two ZombieDs.
The ZombieDs
Unlike the MudGOL fight, you can't run from these monsters (even if they appear in a normal encounter). Fortunately, it's a pretty straightforward fight. You will be teleported out after the battle is won, so don't hold back. HRM4 or FIR3 can make short work of these guys if they are available, and even lower-level attack spells are useful despite their high Magic Defense. Their attacks cause Paralysis and deal out a lot of damage, but not as much as other Dragons you've seen. They have no special attacks or spells, just a lot of HP and a good amount of Absorb. This will not be a difficult fight, even if a pair appear.