How about keeping it as-is, but ensuring that it's guaranteed to be found? The reasonable place for this would be the top level of the pyramid, in my opinion (yes, trolls would still have a harder time).
Pyramid because:
- it already contains random monsters, some rather out-of-depth for levels 13-16
- it's a tradeoff - a later Thrundarr quest gives some nice help for pyramid, you'll need to face the monsters without that
- it's rather nasty for a low level character, but it's still doable.
Alternatively, just reverse the effect. As it was, it was an annoying quest, but not much else.