I like the idea of local algos but k-means sounds like overkill for what seems like a rank ordering problem. It'd be cool though if some kind of semantic clustering of message content were possible.