I think... that's why its called a strategy game 
Yes it would be galling to be beaten 1vs1 just because your opponent got lucky. And vice versa if you're the one about to smash that piffling rival kingdom into tiny pieces with your brand new dragon it would ultimately amount to an empty victory, even while laughing your sadistic little head off.
But I thoroughly applaud this sort of thing in a full on multiple player game. It stands to reason that if you're getting bullied by the big guy you should try and get some others on your side. However if they're simply using you as a buffer to grow a power base of their own... oh well! Such is life in love, war and magic 
So in summary: Yes I would say that this needs to be looked at for 1vs1 play. In a perfect world I would love to be able to toggle the quests in such a way that the mighty relics of yore are not present, so at best the rewards for undertaking such an adventure are worthwhile, but not the crux of a game turning event.
This would also benefit those guys and gals who don't really enjoy these sort of 'random events' in larger games too. But as I said this is a perfect world scenario really, since rebalancing everything like that would presumably take a lot of time.
Ultimately though if the really big rewards are as rare as I've been led to believe, while it may be irritating when it happens to you, I'd just chalk it up to experience and carry on. It wouldn't be nice to see Quests removed all together, after all!