If dismembering Gondor's High Mystic seems too significant to provoke such a blase response from The Elder, I'd go with what Darkgod suggested: make Tannen much less important. Maybe he's a mysterious citizen of Angolwen who recently moved to Minas Tirith, and nobody knows much about him, but the Elder figures that he's a good place to start your quest. Fortunately for everybody involved (except Tannen), the player reveals Tannen for the treacherous scumbag that he is, and they all come away from the experience without any sort of drastic changes in their day-to-day lives, and the broader workings of the nation of Gondor remain unchanged. Setting up relations between east and west is beyond the scope of this particular side quest, but could make for another interesting quest later.
Some thoughts about fun quest design:
1) Failable quests can be good, but ideally failure doesn't simply result in having game content permanently closed to the player. The player can 'fail' this quest, but doing so results in fun stuff: getting dumped in a pit full of demons or a mad wizard's dungeon. That's video game fun, anyway. As a bad example, take the lost merchant quest. Failing results in a portion of the game's content permanently lost. It would be more interesting if we could make something of our failure, like getting to loot the merchant or having a later opportunity to set somebody else up in his building. Experienced players might even have reason to deliberately fail the quest.
2) Decision-making in quests is fun, as long as all decisions are meaningful and lead someplace. For a bad example, take the escort quests. The quests begin with a decision, but why would you ever tell the poor injured Seer to take a hike? I'm not complaining about the escort quests (I love them!), I'm just pointing out the fact that they contain a decision that might as well not even be there.
3) Quests are their own rewards. Why do we help the jeweler purify the moonwhatever? Because we want the moonwhatever pure so we can get sweet loot out of it. Why do we want to do what Zemekkys tells us? Because we want that portal in place. This is something that ToME does well already. Bad examples are what you see in a lot of MMOs: "Hey, go collect 20 pieces of venison for me and I'll give you this magic dagger." Feeling like you're running trivial errands is lame and should be avoided. The player should want to get the quest done without a reward even being mentioned. On a related note, the random ego that The Elder gives you if you manage to kill the orc ambush is unnecessary and usually insultingly weak. I'd recommend removing it and making the lead orc drop something nice.
