To overcome the lack of history together it seems like one has to substitute other forms of bonding experiences; occasional lunches together, conference calls, heavy use of messaging and email, and just making the effort to talk to the people a lot and really get to know them.

My concern isn't so much whether these things are qualitatively equal to the team-building experiences of being stuck in a room(s) together as whether it can work, in practise as well as in principle.