Dynamic Quests
I was thinking, how about a dynamic quest/mission system in addition to the one related to the map? If one player takes certain relics or artifacts that could give him a bonus, other players could try to steal them. I'm not sure how the normal quests are set up, however this could be done in a dungeon like fashion where each faction has their national treasury (and possibly can set up defenses to protect it) and the others can try and breach those defenses.