Update:
I hired the help of a 20th level ranger to track the outcast for me. It swims (Rather Fast I might add) around the island a bit off the shelf area underwater. If you dive in the water you will see the entire island is sitting on a high shielf.. the Outcast wander line is a little ways out from the shielf so you can't really see him from shore.
By swimming fast I mean swimming straight at him for a minute or so when hes near you might get you catch up to him LOL. Luckly azmat is a froglok so I was swimming alot faster then him.
As far as this guy eating a level 60 paladin...
Azmat had just barly dinged 62 (same gear I had since 58 I might add) He was a good fight, but at the end Azmat was still at 70% health and still had 50% mana. I was fully shaman buffed (from my Nabal) but my shaman was not involved in the fight *couldn't get second account to fire up that night*
The quest is up on Wiki currently as well. The helm is..
AC 23
+8 Str +8 Sta +8 Cha +8 Wis +55 hps +65 mana +10 vs Magic
Mind Shield +2%
Healing Increment IV
I would say this quest is worth doing, and in many ways I think its easyer then Soulfire. The Paw trip isn't anything difficult even just boxing 2 45-50 range Toons, and kedge ground spawn can be gotten with a simple Enduring breath and a invis. its not very far from the zone in. Going to update the Wiki since all it gave is /loc
The Outcast is probley your biggest fight as hes in the mid 50s level range. A group of Toons should ahve no trouble defeating him (bring tracker) or just wait until your 60 and solo him (just get some buffs before going)
Foemlo Azmat if you want to see it