As of Patch 4.0.3a the location is now 58.3, 78.5

The cave entrance is at 58,78. It is part of Hive'Regal.

Natalie herself is as far south in as you can go. It's a long, linear, winding hive cave unlike the others. She is at 55,90.

Make sure to get Hive'Regal's glyph, which she is staring at, for the Glyph Chasing quest.

I haven't seen any comments on this but here goes:

This quest likely is a reference to john carpenter's 'into the mouth of madness', in it, some text from a man who was empowered by beings such cthul and the old ones was able to drive people murderously insane who then turned into dark creatures (though you never saw the creatures they turned into).

In this quest, the night elf finds ancient text that drives her murderously insane, text from ahn'qiraj and most likely it is c'thun who has control of her mind.

Dammnnn this, in my opinion, is the single most annoying q i ever did during 2 yrs of WOW. I almost gave up on it. But in the end i found it.

Since Cata expansion the entrance of the cave is located in the southwest corner of the Hive Regal (58,78!). Just follow the way south and on the way u will encounter a Cenarion Scout. Then u know that ur close to Natalia. When u reach the room, just clear all the other mobs and then take out Natalia. She stands at 55,90 inside the cave.
GL!

For people who don't use add-ons with coords, there's at least two cave entrances in the southwestern corner of the hive. If the one you enter has brownish-red walls, you're in the wrong one. Go back out and go further west. It should have greenish-purple walls.

Ok so it took me an HOUR to frikin find the right cave since there are 3, I repeat 3 CAVES in Hive'Regal! And this is specifically for people who don't have cords, since I don't and I know how annoying it is to have to read all the chord comments.You find Natalia and the glyph in the greenish/purple cave located to the very south/west of Hive Regal. Now this isn't the redish brown cave to the very south, and its not the bluish one to the south/east. Its the south/west you wanna look around and you'll find it easy:) Again, all these 3 caves are at the south of Hive Regal, but you want the one to the west.

After around an hour of searching I finally found her. So I'll attempt to simplify this quest. It is easiest to start this quest along with Breaking The Code and Glyph Chasing.

From the start of the cave (Co-ords - 58.0, 78.8) Head straight and take the first tunnel on your left.
Follow this tunnel along, ignore the small side tunnel to your right with the Hive'Regal Burrower, and keep going.
You'll arrive at a crossroads, you want to take the left tunnel which will lead to a room
(Again, ignoring the little side room with the Hive'Regal Burrower).
When you reach the room, continue towards the tunnel directly across the room in front of you, dispatching any of the mobs you need to on the way.
(Note: If you see Cenarion Scout Landion, you are on the right track. He may be stealthed).
Once you reach the end of this tunnel, there is a short tunnel to your right that gets cut off, and a large room to your left.
Mistress Natalia Mar'alith is in the room to your left, kneeling before the quest item for 'Glyph Chasing'.
Please note you do not need to kill all the inhabitants of this room, however if you wish to it may assist with the fight.

Mistress Natalia Mar'alith (Co-ords - 55.6, 90.6) has several spells she casts, none of which are extremely horrible. She can heal herself so whenever you can interrupt her casting that will help. She can cast a fear ability similar to a Priest' Psychic Scream and she has a stun called Blackout, which incapacitates you momentarily.

Best of luck to everyone attempting this quest. It was much easier when I found the right tunnel.

=)
Happy Questing!