Rereading the 4e DMG 2 has given me something to think about: cooperative playing. In most games I've played in and ran, I don't think I've ever seen players work out how their characters met or if they have a prior relationship. Sure, in the games I've ran, I've had players work on their back stories and character motivations, but I've never, that I can remember, had players work out why all these characters were fighting together. They were together because they just were...that was usually my reasoning.
I think next game I run, I'm going to have a pregame sit down where everyone throws around character ideas, story ideas, etc. May even make a random table to determine how characters "know" each other.
Interesting things to think about...
That's why I always like to reread the DMGs at least once a year...always find new ideas.