A common mistake for new players that have reached this level is the absence of their Expansion Registrations. If you've made it this far, be sure to check the Content ID section in the FFXI menu within the Playonline Viewer; the menu that you see before you click the first "Play" button to launch the game into full-screen. Be sure that you see Rise of the Zilart and, if applicable, your Chains of Promathia, Treasures of Aht Urhgan, and Wings of the Goddess expansions in the list of registered Expanded Services. Guddal will not respond to you if you attempt to trade the keys prior to registering the Rise of the Zilart expansion.
You have 2 options when you first talk to him, pay 148,000g or take the "Adventurer's Deal" (do a quest).
Note: If you back out of the dialog before selecting one of the two options, this may glitch his conversation, so that talking to Guddal again doesn't ask which option you want to choose. Zoning will reset this glitch, and allow you to select the option normally.
Once all three chest keys are obtained, trade them to Guddal for the key item.
Giddeus: Stay to the right and make your way to the cave at (G-7). Head left after you enter and drop down the hole concealed by bramble. Walk outside the tunnel and follow the path all the way to the bottom of the map, taking care to not fall down. The very last room contains all of the chest key mobs.
Palborough Mines: Take the elevator at (I-8) to the third floor and make your way to the area just before Waughroon Shrine. The mobs spawn after the river around (H-9), in the four rooms and the path leading up to the zone.
Foes that drop the required keys can be soloed by most level 25 or higher Damage Dealing jobs.
Mage jobs may require additional support if attempting this quest at 25.