The wild wild east
You are met by Harno, Herald of Last Hope, who delivers a letter from the King of Last Hope, then vanishes. He gives you the sealed letter from the king; you will need to Use it to read the letter. Oddly, it will be under runes/inscriptions in your inventory.
The note will indicate the Staff of Absorption was taken in a raid and will mention Golbug (whom you just defeated) and a portal. It so happens there is a farportal in the room just beyond where Golbug was waiting. Didn't you just pick up a Orb of Many Ways? Walk into the portal and activate the Orb, and off you go.
This quest is completed as you exit, and you begin Strange New World as you arrive in the East.