IIRC the portal in Stone's fortress is fairly high up, on a small platform.
You can also return to Broken Valley from the start of the fjords (up the path from the Grand Knight teleporter shrine), either walking or flying.