Whether the quest fails or not is irrelevant; you just need the key, and Williams doesn't decide to rush downstairs (though the 4 rangers that come upstairs and the 3 black ring warriors at the bottom) until you have it.
If you have the battle tower, you should just need to fly a bit south east of the quarry tower to reach the mine entrance.
