Interesting question came up.

When do the heroes actually get the red runekey?

RtL pg17 and SoB pg19 (more or less word for word)
Unless otherwise stated, the leader on each dungeon level carries a red runekey. Upon killing the leader, the heroes immediately receive it and can open the corresponding red rune-locked door.
That's fairly clear.

But what if there is more than one Leader?
Do the heroes have to kill them all? Or does the first one killed have the runekey? I can't find anything to judge. There is nothing in the FAQ or GLOAQ. Yes, you get the CT and cash reqard for each leader, but that's a separate thing entirely.

In RtL levels this practically never came up. Nearly all the multiple leaders had special rules so that you had to kill both/all or they were linked or one was obviously the main boss. Possibly exceptions off the top of my head are the two hellhound leaders (fire and ice) and the Trial by Fire with it's three levels (you still need to kill the dragon and the hellhound just to get to the portal but unless there is special text maybe you could simple run around the demon then).

However, it certainly came up last night, in an awkward combnation with some other potentially broken rules on a SoB island level. There'll be a separate topic on that.

Further Research:

RtL has 8 levels with multiple leaders.
All 8 have clear and specific instructions for when the door unlocks (or has the door already unlocked).

SoB has two dungeon levels with multiple leaders. Both have specific instructions for the red runekey.

All rumour levels for bothe camaigns have clear instructions.

There are 10 island levels in SoB.
9 of them have specific instructions for unlocking the cavern.

So it is only this specific island level that is unclear.
There are two leaders and no reference at all to the cavern entrance, which leaves us with the rules quoted in the first post.

still in the dark...

My gut reaction is that you would have to kill both leaders. The rules are sadly silent on this specific question, but as you point out there's really only the one occurrence where specific map rules don't explain how it should work. So my instinct would be to say you have to kill both. Having read the other thread, I would agree that this could be seriously difficult, especially if the OL is paying attention to his options. My response to that would be to remember that the heroes do have the option of fleeing a dungeon (or island in this case) if pushing forward would cost them too much to be worthwhile.

Could this level have been written better? Yes, probably. Being written as it was, however, it's mostly just a trap for heroes too hardheaded to recognize when pragmatism is the better part of valour.