Wow some amazing thoughts and ideas.
Rufalus yeah Alternative Mythology methods would be ideal which links in with what Kawab said thief could be that alternative potentially.
Zider, you have a good point just by opening up those areas they open up a lot of the game. they can put quest flags perhaps make a little story arc for each dungeon and by doing that make the game feel that little bit bigger. and even people repeating dungeons cant say anything cause in the story the pirates are dead so that's a legit idea.