AT solves these problems. Even if AT turns out to be a bust, they have an excellent architecture.
It's true that this solution doesn't work for private posts and DMs, but the n in O(n^2) is much smaller there, so I don't think it's as much of an issue for personal data servers to communicate directly in those cases.