A useful mechanic is to provide each player with only a part of the solution. This works especially well if certain classes can have information others don have. For example there could be a sort of "seer" class that can get information about the enemies that other players cannot. This means that the other players in order to succeed must have information from the seer. Another option is to require cooperation by making the game strategic, you can easily see that in a game like WoW players must first communicate who can "tank" and who can heal. This means that they communicate a bit before they attack and during the fight they might try to attack at the same time. What you should avoid if you want a lot of coordination is making action speak much louder then words, in team fortress for example it's often faster to inform your team mate that you are not a spy by shooting then by saying something, that means that players are not talking but taking actions (through that might not be so bad). Lastly it's important that the phasing is not so fast that the players cannot speak in (so if it required 2 seconds to get out a message in a fast fps then nobody is going to do it).
Another thing to to do is allow players to organize a form of groups/clans/alliances. If people are easily able to find the people they enjoyed working with again then they are likely to stick together in the future.
Additionally think about giving them items to trade with, this works especially well if certain items can only be used by certain classes, for example say we have a healer class who uses a healer staff. Let's say that this staff can be upgraded but doing so require a set of really hard to get items. These items drop at random time from all types of monsters. Of course now every player is going to find these items meaning that they can try to sell or trade them with the healers thus encouraging cooperation.
A last interesting mechanic I found a long time ago was where players would be able to "share" with others, sharing meant that they were giving a part of their xp to the players they were sharing with and meant informing the other player that that player had "fallen" meaning he was in dead and would require a healer to bring him back up. The healers were encouraged to do so because doing so would mean that players sharing with them would be quickly back on their feet giving them xp (this works well if your healer class is otherwise incapable of getting xp).