First, make your way to this spot in Tanaris. Then, start swimming south/west along the coast.
Before long you will come to a beach with many elite turtles. Continue southwest. Follow the mountains.
After awhile you'll come to a second, smaller beach.
On this beach there's a spot that, if you have any experience exploring whatsoever, just screams "CLIMB ME". Do it.
Up top, point yourself to the west.
Follow the screenshot. Proceed west. When you can find an opportunity to get up on the mountains to your left, do so and continue.
When you reach here, chug your trusty Noggs, jump down, then float down the cliff where the line is dotted and proceed.
We can see part of the zone now, but don't go over there yet!
Follow the screenshot once again. The path there is extremely narrow, but it widens up a bit very quickly.
Here's where you want to jump to. (Nogg, of course.)
On the same Nogg, leap over the abyss and into the zone.
Behind the Scarab Wall! You'll notice that the minimap texture doesn't match up at all with what's back there now, since the AQ patch. Unfortunately it's not nearly as interesting either, but it's still a neat place to look around in. There is a small section of uninstanced AQ20, but the portal is blocked by a few invisible walls. It may be possible to get into uninstanced AQ40, but I haven't really tried yet so I'll leave that as a challenge to you.