The quest idea actually can work- it simply needs a slight work around. Let's break this down-as we know, each player's city is it's own instance. The player's army remains there unless the player chooses to move somewehre with it.
So, say they are on some epic quest (taking down a capital maybe) with a few friends when an orcish player gets a quest to take down his city. My suggestion would be to create an exact replica of the defending player's army and station it in the city if a foe gets a quest to take down the city and let a hard AI defend until the player completes his mission. When he does, he can feel free to take over things with the current forces in the city or let the AI fight it out with the other player.
Alternatively, a message could notify the player if such a quest came out, but I think it's far more interesting this way. If the player just received a message, their plans would be interrupted and he would be forced to pay tribute if he wanted to continue, or just forfeit entirely. While this happens under normal circumstances, nobody would be prepared for this sort of quest, and thus not many sieges upon cities would actually take place. The overall point of the game is the interaction between players and cities- however, far to many tributes will likely be payed a day as it is. This sort of quests should have its own features and circumstances that can allow it to change the normal way things are done. The normal options- (paying tribute, fighting) can still be availiable- this will just lower the amount of treaties payed.