If you want to get your teleporter stones back as quickly as possible, wait awhile before entering the castle (I did most of the quests in Rivertown and Verdistis, some people also recommend clearing some of the Dark Forest) and clear out the Rivertown sewers. After entering and leaving the castle, proceed with the main plot quest you will get to rescue Zandalor, then let him teleport you somewhere.