Trade some crystals for Rank Points (three stacks of crystals is enough to unlock this mission) or repeat certain missions instead of trading crystals. Basically, your Rank bar in your profile has to be 50% or higher. You don't have to go to your nation to trade crystals, the conquest overseers in Jeuno will accept them as well.
Report back to your embassy in Ru'Lude Gardens.
The gate guards will not hand out this mission, this mission is handed out by your embassy instead.
Talk to your ambassador for a cutscene to get the Archducal audience permit that lets you see the Archduke.
If doing this mission after changing allegiance, during the cutscene, it will be mentioned that you already have an Archducal audience permit and that you dont need another. It will end the cutscene by saying... You have accepted the mission. Continue onto next step.
Head to the Duke's Audience Chamber (H-6) for a cutscene. He promises you an Airship pass in exchange for 3 Magicites from the beastman strongholds. In the cutscene Mawl'gofaur will give you the key item Letter to Aldo. (If redoing this mission after changing allegiance, it is important to get this key item again and talk to Aldo before heading out to the strongholds.)
Collect 5 key items to access the three Magicite locations you will travel to.
-Davoi: Crest of Davoi
-Castle Oztroja: Yagudo Torch
-Beadeaux: Coruscant rosary, Black Matinee Necklace, Silver bell
(You need to talk to Aldo before you can obtain the Crest of Davoi or Yagudo Torch
Please Note: If you are doing this after changing allegience, you will have all 5 of the key items in your possesion already. You will still need to do the cutscene with Aldo, but then you can just proceed to collecting the magecite. No need to kill beastmen to get items or run around trying to collect the bell and necklace again.
Also: If you receive the message 'The Silver bell, Coruscant rosary, Black Matinee Necklace, glow faintly.' when you examine the door to Qulun Dome, just move closer and re-examine the door.)
You must have completed the Tenshodo Membership quest in order to be able to gain access to the back rooms of the Neptune's Spire.
Talk to Aldo in the Neptune's Spire to receive the Silver bell.
Coruscant rosary and Black Matinee Necklace
Talk to Sattal-Mansal, a Tarutaru who stands by the door to Aldo's room. He will ask you to bring him a Quadav Charm and a Quadav Augury Shell.
This will activate the quests Mysteries of Beadeaux I and II.
Upon completion of these quests, he rewards you with the key items: Coruscant rosary and Black Matinee Necklace.
Crest of Davoi
Baudin (G-8) in Upper Jeuno requests that you bring a slice of Coeurl Meat back to him.
This can drop off any Coeurl or can be bought from the Auction House.
Trade him the Coeurl Meat and he will give you the Crest of Davoi.
This also completes the quest, Crest of Davoi.
Talk to Paya-Sabya in Upper Jeuno (I-8), who stands between the armor and weapon shops, for a cutscene.
Head to Muckvix's Junk Shop at (H-9) in Lower Jeuno and talk to Muckvix in the back room and he will give you the Yagudo Torch.
Ensure that you have the Crest of Davoi before leaving for Davoi.
Upon entering Davoi from Jugner Forest, follow the right wall until you come to a T-intersection, go left. Continue on till you cross a bridge at (H-7).
Continue forward until you come to an intersection at (G-7), where you should make a left turn.
You will see the Wall of Dark Arts, which will be guarded by Orcs, and sometimes a Wolf Bat.
Kill the two Orcs or cast Invisible on yourself and walk up to the wall and drop it when they are not looking.
Activate the wall by inspecting it. If you get aggro after you inspect the wall, continue to pass through until you zone into Monastic Cavern, which is just a few steps away.
It is possible to tractor someone through the wall of dark arts.
Follow the path safely to the end (there are no mobs in this part of the cavern).
At the end of the path, you will find the Magicite. Click on it for a cutscene.
After the cutscene, you will receive an Optistone.
If you have already completed this mission for another nation, you do not need to kill the NMs to complete the "Mysteries of Beadeaux" quests, you may proceed directly to the magicite.
Two NMs need to be killed to proceed with this mission, fulfilling Mysteries of Beadeaux I and Mysteries of Beadeaux II for the two key items necessary to access Beadeaux's Magicite.
These NMs are De'Vyu Headhunter and Go'Bhu Gascon
De'Vyu Headhunter drops 1-4 Quadav Charms when killed, and Go'Bhu Gascon drops 1-3 Quadav Augury Shells. Be sure to bring some combination of players able to take down level 45 NMs.
Upon entering Beadeaux, hug the left wall until coming to a tunnel. Go down the tunnel, making two right turns to come to a "Mute" machine, which will inflict Silence on any player that checks it.
Turn around and go straight until a T-intersection, then turn right, coming to a room with an "Afflictor" machine, which will inflict a powerful Curse on any player who is not silenced.
Take the northern exit from the Afflictor room, and go straight, eventually coming to a spiraling tunnel leading back above ground. Head south, then east. Another Mute is here; refresh your silence status before turning south again, hugging the right wall and passing an Afflictor.
There is a ramp at (E-10) that leads to the upper level; take it and cross the nearby bridges across two land-island formations, passing directly above another Afflictor. After the final north-south bridge, you are free of the Afflictors and your mages are safe to use their Echo Drops.
Turning right and heading Southeast will lead to De'Vyu Headhunter at (I-9). Kill this NM, then hug the right wall until coming to Go'Bhu Gascon at approximately (F-6).
It is possible, but sometimes difficult, to pull Go'Bhu Gascon from the bottom level, near the entrance to Beadeaux.
Once everyone has both items, head back to Lower Jeuno.
Report back to Sattal-Mansal and trade both items, one at a time. You will receive the final key items that let you enter the Magicite room of Beadeaux.
Re-enter Beadeaux, hug the left wall, and do not open any doors.
Only people under the level of 35 should need Sneak.
You will go into the lower level. Take a left turn at the intersection, and you will zone into Qulun Dome.
After you zone, just head straight and open the door. Inspect the Magicite.
After a cutscene, you will receive another magicite, the Aurastone.
Also: If you receive the message 'The Silver bell, Coruscant rosary, Black Matinee Necklace, glow faintly.' when you examine the door to Qulun Dome, just move closer and re-examine the door.
Enter Castle Oztroja and head to (I-8), use the levers to open the door and head up the stairs.
One lever opens the door and the other will land you in a trap pit below which you will need Escape to get out of, or you can tab around to find the point to open the secret door and walk back up, but it's a long walk.
The correct lever changes daily (Vana'diel time). An easy way to check which is the correct lever you need, have one person stand in between both levers and as you check one, run out from between to clear the door if it happens to open.
To avoid the trap, target a lever, and stand between the levers, facing south. The moment you hit the lever, run forward. You should be able to get away from the trap doors before they open.
When you reach an intersection at (I-8) of the second floor, make a right turn. Ignore the turn at (I-7) and continue going straight, eventually you will reach (G-7) where you will head outside.
You will be at an overpass. Go right and take the tunnel at (I-7). Once you enter this tunnel you will be on a different map. Keep going forward, down lots of stairs.
Past here, unless you are level 60+, you will need to have Invisible
Once you reach an intersection at (H-8), make a right turn and go straight, left at (G-8), then make the second left at (G-9), go forward, ignoring the left tunnel, hugging the right wall around one corner, then a left at the next intersection, you will come to the torch door. (Corner at H-9)
Either wait for them to turn their backs, or clear all Yagudo that are near the torch door, as everyone must light the torch to get through.
To light the torches, each person must drop invisible, and stand between the torches in front of the door.
You don't need to be in between the torches, just stand about a person away and in front of a torch in order to light it.
If you are too close you'll get a message that says you can't reach the torch.
Once you light a torch, you will automatically go through the door.
You may encounter a few more Yagudo just past the door. While passing the door will erase hate, it is still possible to catch aggro through the door.
Once past the door, turn right at the intersection of (H-10) and you will find another brass door. Simply click to open it. If any aggro happens, the zoneline is just past the door.
Once inside the Altar Room, just head straight as there are no mobs. Target the Magicite and watch a long cutscene.
After the cutscene, you will get the magicite, Orastone.
Return to Jeuno
Return to the Archduke and for a cutscene. At the end of the cutscene, you will get your Airship pass--or 20,000 gil, if you already have an Airship pass.
Return to your embassy (in Ru'Lude Gardens) and talk to the person behind the counter. They will give you Rank 5, the key item Message to Jeuno, and 10,000 gil.
You will be unable to unlock new missions once you obtain Rank 5, as Mission 5-1 starts instantly. Report back to your home nation for further instructions.
I dug a little deeper and realized there was a WHOLE lot more to it than I'd remembered. This is a pretty lengthy quest. Suggested level is 45, but you'll probably want to try to find help. If you're new, you could try joining an XP party with another job (not the lv. 50) and theres guaranteed to be someone with a 75 job, they might offer some assistance. Don't let the whole thing bog you down, its a pretty straight forward quest. Just follow the steps 1 by 1 and it won't seem so bad.
Also for Maat, at level 69 you'll have to fight him in order to progress any farther. Its basically a 1 on 1 fight, hes going to use hand-to-hand, but he'll have all the job abilities and spells of the job you're fighting him as. Also, you don't get to use a subjob. you can't do it as a team, it has to be 1v1.
Good luck with your airship quest, if I was on your server I'd offer to help. =/
Edit: Theres a nice thread called Need A Little Help? on these diabolos server forum with a few people offering their hands to noobs in distress, you might try asking them.