Warcraft 3 Frozen Throne Walkthrough for Night Elf Sentinels:
Chapter 4: Wrath of the Betrayer
Main Quest: The Runner's Transport
Optional Quest: The Naga Excavators
Moving on to Maiev's mission, move her group to the south. Kill the Naga guard and excavator there. I didn't bother with the staff. Maiev is powerful as is and the base is just fine so the staff is not needed. Switch back to your base when you see you have enough gold to reinforce your troops there. I won't mention them again as the only thing that really changes is an eventual aerial assault, so keep enough archers on hand to deal with that inevitability.
The path for Maiev changes to a western one, and you will need to down some Mur'Guls. Take the southern stairway and fight your way through the Naga sorceresses and snap dragons there to find the second excavator, which has a staff of negation. There is also some good gold there to help you buff up your base. Protectors might come in handy because they don't take up population.
Maiev should head on toward the transport ships. There will be a third excavator to the east, just after you receive the huntresses as reinforcements. This excavator drops an orb of slow, which is a great item that slows enemies down while giving a +6 bonus to attack. When you finally reach the transports you'll be given 2 ballistas, 3 hippogryphs, and 2 transport ships. Use a druid to cast rejuvenation on a single hippogryph to make it tank, then take it to the south to draw the fire of the coutl. The other 2 should join in immediately after. Once the coutl are gone, board the transports and head south.
There are 1500 gold coins to be found if you take the southern ramp where you can first unload your troops. I wouldn't bother if your base is doing fine. Still, this is a good place to start your assault on the Naga to the north. Take out the Sirens as they come and hit the hydra pits that shoot at you with your ballistas. The gate must come down to allow passage of your ships. If you take a hippogryph to the southwestern corner you can see a giant panda that will run off and drop a cloak of agility +3. You can get there by blinking, or using a transport to go up the waterfall. Further north you will encounter more naga and a second gate. Finish off the guardians there then send the runner on to the ocean.