Benefiting the player in most any way will push toward that, or at least it should. Giving the players, that are most active in doing this, special recognition is a great idea and way to pull them in. Maybe changing the game in ways that allow everyone to notice, such as mprogs speaking of victories or defeats, battles and things like that. Giving mention and making the players feel like they are a big part of the game for doing so. Almost all of my ideas I am mentioning are branches from your ideas, if not exactly what you have already covered though. Hopefully it sparks something by me mentioning some small ideas.
How about writing a compelling storyline so players WANT to team up, and while your'e at it, code the game mechanics to be group oriented, rather than everyone soloing in competition with everyone else?