Why not just make Majesty with real people substituting for the adventurers? The characters in Majesty don't listen to direct orders anyway.
Oh right, nobody played Majesty because they suck (the people, not the games).
In WoW guilds you have a guild leader that dictates what dungeon the guild runs, who fills which role, and who gets what loot, and people go along with it. Gamers are notoriously bad at getting organized just for the sake of some abstract victory, but they're notoriously greedy when it comes to abstract in-game currency. As for the griefing, you say griefing, I say sabotage. You can't just give up on a good game design because you're too weak to deal with the sort of people it would attract. You build the game to fight back. As long as a merc sticks to his contracts, does them well, and behaves, he gets rewarded with prestige as well as money, which makes his service more enticing to potential buyers. If a Merc goes rogue and starts attacking things that he is not authorized to be attacking, the victim can choose to charge or pardon him (in case there was a good reason for the attack). If the victim charges, the Merc's prestige drops and they get marked as on probation. If the Merc makes a regular habit of this, his Merc license goes poof and he is now full-fledged Rogue. A Rogue loses all Merc privileges, they don't appear on the registry, they can only offer their services under the table (which means no automated contract system that guarantees payment on mission completion), and they can't travel freely. They are now just a wandering gun doing whatever gets their rocks off, but any commander can set his policy to kill rogues on sight, if that's what he wants. If a Rogue gets REALLY bad, they would start acquiring a bounty. Now the commanders are the ones getting paid, and the FPS-player is the target. It isn't just revenge-killing any more, the whole server would want their head. A griefer could get away with tricking one or two commanders and backstabbing them, but then they would be marked unless they go to GREAT lengths to clear their name. The kind of lengths that would take a month or more to complete, like grinding rep to exalted in classic WoW. They could buy another account, but that would mean starting over and paying for the game again. If that's the price they're willing to pay...
Pro tip: most griefers aren't. They'll cry about getting banned on the forums, get banned from the forums, go rage about how much the game "sucks" and then move on to something else.
Also, props to Yahtzee for articulating an idea I've had for years.