You can't get this quest over a certain level it seems. This plays hell with a person who loses their key. May be intentional, but if not--theres the suggestion to change it.

There's no level limitation, it is however doable only once in a character's life-time.