If you're doing this quest line at level 60 (as most likely will be), Hetaera really isn't too hard. Only a level 55 elite -- as a warlock, I was able to solo via DoTs and chain fearing...not too many mobs in the area to get proximity aggro, after all. Other classes may have an easier or harder time, but worst case just find a warrior (or a healer if you are a warrior) to help you out and the problems will be minimal.

""at 56,45 is a place called 'Hetaera's Clutch'...hmm, guess what that is?""

A stone building with no apparent entrance and no Hetaera? She roams in an area north of that.

Good luck finding it ;)

In patch 2.3 this quest is no longer a group quest. Hatera is not an elite mob.

I found Hatera at 58/47. I submitted a picture. She has a nasty bite that last for 3 mintues, Physical damage taken is increased by 5, and 15 nature damage every 10 seconds. I soloed this at lvl 60 Nightelf rogue with 1/4 life remaining. I used crippling poison and wound poision.

This is a quest in a chain of 23 that runs pretty much all over the map.
However, it all starts with the Fallen Hero of the Horde.
(Hat tip to Xeir for the initial connectors between chains.)

Technically, it's four chain quests that tie into each other:
Chain 1:
1. https://vanillawowdb.com/?quest=2784 Fall From Grace
2. https://vanillawowdb.com/?quest=2621 The Disgraced One
3. https://vanillawowdb.com/?quest=2622 The Missing Orders
4. https://vanillawowdb.com/?quest=2623 The Swamp Talker

Chain 2:
1. https://vanillawowdb.com/?quest=2783 Petty Squabbles
2. https://vanillawowdb.com/?quest=2801 A Tale of Sorrow
3. https://vanillawowdb.com/?quest=2681 The Stones That Bind Us
4. https://vanillawowdb.com/?quest=2702 Heroes of Old
5. https://vanillawowdb.com/?quest=2701 Heroes of Old

Chain 3:
1. https://vanillawowdb.com/?quest=2721 Kirith
2. https://vanillawowdb.com/?quest=2743 The Cover of Darkness
3. https://vanillawowdb.com/?quest=2744 The Demon Hunter
4. https://vanillawowdb.com/?quest=3141 Loramus
5. https://vanillawowdb.com/?quest=3508 Breaking the Ward
6. https://vanillawowdb.com/?quest=3509 The Name of the Beast
7. https://vanillawowdb.com/?quest=3510 The Name of the Beast
8. https://vanillawowdb.com/?quest=3511 The Name of the Beast
9. https://vanillawowdb.com/?quest=3602 Azsharite

Chain 4:
1. https://vanillawowdb.com/?quest=3621 The Formation of Felbane
2. https://vanillawowdb.com/?quest=3625 Enchanted Azsharite Fel Weaponry
3. https://vanillawowdb.com/?quest=3626 Return to the Blasted Lands
4. https://vanillawowdb.com/?quest=3627 Uniting the Shattered Amulet
5. https://vanillawowdb.com/?quest=3628 You Are Rakh'likh, Demon

Completing the entire chain gives you the following:
103,685XP at appropriate level
Shard of Afrasa
Enchanted Azsharite Felbane (Dagger, Sword or Staff)
Necklace of Sanctuary
Demon's Blood
Demon Hide Sack

This quest is now kind of unintentionally amusing. Hetaera was originally elite, but certainly no longer is. Meanwhile, the Servants of Arakkoroc, which patrol pretty much the entire water area, are giants about one level lower than Hetaera . . . and still elite. Meaning that any one of them is easily a match for Hetaera herself. In fact, when I first found Hetaera, there was a Servant literally standing on top of her.

I can only assume that the first Commandment of Arakkoroc is ""be incredibly lazy and get adventurers to do your work for you"", otherwise Hetaera would be a green smear by the time you got there.

On top of that, the Servants - who, naturally, will attack you on sight - are a much larger threat than Hetaera herself. So I'm guessing Arakkoroc has the Hetaera situation well in hand at this point, he just likes giving people annoying missions and then making life hard for them.

This quest DOES count for Loremaster of KALIMDOR