This fight is no longer capped at level 25 since the Feb 2011 mini update.
If you skipped mission 2-2, you may need to trade crystals to a Temple Knight NPC for rank points. You do not need to completely fill the rank point bar; three stacks of crystals should suffice.
Talk to the gate guard to obtain this mission. The gate guard will send you to Halver inside the castle. Halver will give you the Letter to the Consuls and tell you to travel to Bastok and Windurst and go to the embassy. Which nation you visit first is up to you.
Head to the Consulate of San d'Oria in the Metalworks at (I-9) on the second floor and speak to Savae E Paleade to activate a cutscene.
Enter the Department of Industry adjacent to the President's Office and speak to Pius.
Walk to the Craftsmen's Eatery at (G-9) and speak to Grohm. He will give you a few Pickaxes for your mission.
You are able to buy additional Pickaxes from different shops to help with the mission. Pickaxes have a chance of breaking when mining so having more will save you the trip of returning to Bastok and purchasing more.
Everyone in your party must have this item to enter the BC, or have completed 2-3 previously in their current nation of allegiance. One person cannot get others into the fight who do not have the Dark Key, even if they are currently on this part of the mission, unless they have completed the mission in their current nation of allegiance.
Once the Black Dragon is defeated, another cutscene will happen. When you exit, you will be transported to West Sarutabaruta. Report to Mourices at the embassy. You will be rewarded with the key item Kindred Report. The embassy will tell you that this part of mission is done. It is time to talk to Halver.
The respawn time for Zhuu Buxu the Silent is 15 minutes. You will need to wait until he appears again to gain the second Parana Shield.
After obtaining 2 Parana Shields, make your way to (F-7) and speak to Uu Zhoumo to give the Shield Offering.
Return to Windurst and speak to Kupipi. (Just found out that this is optional by accidentally skipping the step. You can go straight to trading the 2 Parana Shields to Mourices after giving the offering to Uu Zhoumo.)
Return to the Consulate of San d'Oria and speak to Mourices. Trade him the Parana Shields as proof of your completed task.
After you've won the BCNM you can exit back into Palborough Mines travel a short distance on that map to H-8 where you can board one of the lever activated ferries and return to Zeruhn Mines which is connected to Bastok Mines.
Return to Bastok and speak to Savae E Paleade to obtain the Key Item: Kindred Report and to complete this portion of the mission.
Return to San d'Oria and speak to Halver to complete this mission.
Visit the faraway nations of Bastok and Windurst and receive official recognition as an adventurer.
Mission Orders (Windurst to Bastok)
Journey to Windurst
Bring an offering (a shield) from Heavens Tower in Windurst to the Yagudo treasure room in Giddeus. To uphold the honor of San d'Oria, claim two of the same shields from the Yagudo on your return.
Journey to Bastok
Reports indicate that the Quadav who inhabit the deepest levels of Palborough Mines are up to something. An official named Pius will instruct you further.
Mission Orders (Bastok to Windurst)
Journey to Bastok
Survey Bastokan mining technology, and bring some mythril sand out of Palborough Mines. An official named Pius will instruct you further.
Journey to Windurst
Oust the giant monster that dwells deep inside the Yagudo realm of Giddeus.
SPOILER WARNING: Details about a quest, mission or other Final Fantasy XI in-game storyline follow.
Riault : You mission is to go to the Palborough Mines, currently under Quadav control, and take a sample of the dwindling resource called mythril.
Riault : To be precise, we need you to bring back an onz of mythril sand.
Riault : Thanks to our agreement to mutual cooperation, Bastok is allowing us to send you into the mines. Your true objective is to gather as much information as possible on Bastok's advanced technology.
Savae E Paleade : If it were up to us, we would want you to go to the mines right away, but we were told by the Bastok authorities that you must report to them first in order to receive authorization.
Savae E Paleade : I know you'd rather do without all the red tape, but bear with us and report to the Bastokan official named Pius. He can be found in the President's Office.
Savae E Paleade : I must warn you that we thought the Humes were a reasonable people before we came here...but we've found that this is not always the case.
Savae E Paleade : Their talent at making profit is incomparable, but their sense of duty is somewhat lacking. In fact, even their officials can be troublesome. For the sake of your mission's success, try to be patient.
Grohm : Hm? What do you want? Hey, you're not from Bastok, are you?
Grohm : What!? You're San d'Orian, and you listened to what a Bastokan official told you to do?
Grohm : Hah! I have no idea why that Hume sent you here...or why your consulate sent you to him in the first place.
Grohm : You better listen good. A lot of us died trying to win the Palborough Mines back from the Quadav...
Grohm : It might not matter to a foreigner like you, but they always send us Galka to do the dirty work!
Grohm : What gets me the most is that they don't even think about it twice! Even if you haven't been here long, you must've seen how they treat us.
Grohm : Never mind. Shouting at you won't change anything. You wanted to know about refining ore, right? It's easy, but you have to remember the steps.
Grohm : Here goes:
1. Get a chunk of mine gravel.
2. Put that into the upper part of the refiner.
3. Take the onz of mythril sand out of the lower part of the refiner.
Grohm : You can either buy a chunk of mine gravel from someone, or get some by using a pickaxe on a mythril seam inside Palborough.
Grohm : The refining machine is so big, its upper and lower sections are on different floors. Put a chunk of mine gravel into it on the third floor, and it'll produce an onze of mythril sand on the second floor.
Grohm : I know it sounds simple, but it's not. You've got the Quadav to deal with, and they're everywhere.
Grohm : Here, take these pickaxes. Good luck. You're gonna need it.
Lion : Hey, you're an adventurer, right? From another country?
Lion : Sorry, I couldn't help but eavesdrop. I'm going to the Palborough Mines, too.
Lion : Don't worry, I won't get in your way. I don't think we're going after the same thing anyway.
Mourices : So you've come all the way from San d'Oria, eh? Your dedication to serving the motherland is most admirable.
Mourices : This mission on behalf of the Windurstian government displays our country's level of friendship towards Windurst.
Mourices : Forine, please explain to the brave man here what the mission entails.
Forine : Yes, Consul. Allow me to explain Windurst's request...
Forine : A giant monster has appeared in the depths of Giddeus, the borderland to the theocracy of the Yagudo beastmen. The Windurstian government wants it exterminated.
Forine : You are to receive a key from Heavens Tower in the Windurst Walls district and head to the innermost part of Giddeus, where the creature awaits.
Mourices : Ha-ha! What a jolly tale that is. A ferocious monster appearing in the heart of Giddeus, scaring the Yagudo so much they ask Tarutaru to help them?
Mourices : It's most fortunate for those beastmen that the Windurst government had sought amicable relations with them in order to maintain the peace of their country.
Mourices : What? Don't tell me you hadn't heard of the Windurst's little peace pact with the Yagudo?
Mourices : Of course, we San d'Orians have no need to show to those vulgar beastmen any courtesy whatsoever, but this is an agreement between our two countries, so we have no choice but to go through with it.
Mourices : So go ahead and exterminate the ferocious monster plaguing the depths of Giddeus, but don't think you have to hold back from also giving those whining beastmen what they deserve.
Mourices : Anyway, enough chatter. Godspeed on your assignment.
Forine: The mission from the Windurstian government entails the oblation of magic armor to Giddeus, the frontline to the abode of the Yagudo beastmen.
Forine: A magic shield will be handed to you at Heavens Tower in Windurst Walls. Your orders are to deliver it to the Yagudo treasure chamber, deep in the underground of Giddeus.
Mourices: Have you had the misfortune of meeting the Yagudo yet? They have made a nasty practice out of ganging up to attack the travelers who pass through Sarutabaruta...
Mourices: These are the same beastmen who sided with "the Kindred" twenty years ago, and killed many of our comrades in the war.
Mourices: However, the Windurstians have grown too complacent and show their love of pacifism--even if it is nothing more than a one-sided façade--by forming amicable relations with the Yagudo beastmen.
Mourices: And now they dare ask us proud San d'Orians to carry a tribute to a pack of beastmen. It would almost be laughable if it wasn't such a slap in the face.
Mourices: However, this mission has to be accomplished as part of our pledge to Windurst. We Elvaan are not ones to break our promises, are we?
Mourices: The situation is most exasperating. However, I must command you to go and give the Yagudo their magic shield. But at the same time, I entreat you to deprive the other Yagudo you meet along the way of two of their shields, making up for the imbalance.
Riault: We need to find out who or what is rallying the beastmen, and at the same time, make it look like we are cooperating with Bastok.
Riault: That is why we need you to go investigate the Palborough Mines. They were once the property of Bastok...but these days, no sane Bastoker would come within a malm of it, given the choice.
Savae E Paleade: If it were up to us, we would want you to go to the mines right away, but we were told by the Bastok authorities that you must report to them first in order to receive authorization.
Savae E Paleade: I know you'd rather do without all the red tape, but bear with us and report to the Bastokan official named Pius. He can be found in the President's Office.
Savae E Paleade: I must warn you that we thought the Humes were a reasonable people before we came here...but we've found that this is not always the case.
Savae E Paleade: Their talent at making profit is incomparable, but their sense of duty is somewhat lacking.
In fact, even their officials can be troublesome. For the sake of your mission's success, try to be patient.