With a little help from a cleric and a druid or shammy this quest can be done as early as lvl 16. All you need is invis at 16, enduring breath (druid) and invis undead (cleric). Or if you have the money you can buy potions that do all 3 effects. Key is to make sure the Hand room in Lower Guk is clear before that part of the quest..if not just shout out you need it cleared to do the quest and you'll only have to wait 5 minutes at most. The trick is patience and planning.
However I did mine at lvl 20 as the ports really help speed up the movement across all the zones.