there are staircases not show on the maps leading up/around the horn up to those levels..
I think it says they are hidden.. but don't recall what/ if any DC it was, so i guess your discretion.
The stairway up to the room with Hexor and Vexor has a hidden door leading into either the second or third floor throne room.
On that floor is a stone dude, if they realize it's someone who has been turned to stone and fix him he will spill everything about how the teleporters work.
If they don't find the secret passage leading to Hexor and Vexor then make em fly inside. They're at least 5th level, so some fly spells should get them inside. By flying they should find at least 3 entrances depending on how high they go.
IIRC, and it's been a while since I played that, there is a staircase that goes from the caves, two external staircases, a hole or two in the floors.
There is no easy way to go between floors. It is a horribly designed base of operations. Apparently done on purpose to keep the peons and clergy separate.
Our group caved in the stair case leading from the cave to Hexor and Vexors room.
We decided it created too easy of a direct path to the ritual area. We also placed a door leading to the H and V room so that we could actually get to ritual space.
Also we keep Hexor from any combats and use his at will D doors to move people in and out of the horn. We rarely use the teleporter outside because we don't want anyone to overhear the command words.