[michaelt]

You could divide the country into segments, and a person gets to talk to everyone in their segment.

Obviously, you'd want smaller segments in areas with a high user density, and larger segments in areas with low user density.

You could generate segments with something like EM clustering. You probably wouldn't want continuous segment recalculation, or two people could be split mid-conversation when neither of them had moved.