1) They've mentioned maybe using XMPP, which is federated and seems to work ok.
2) It's worse than that, search for John Smith on facebook and the top result will be the one in your social circle. So a central directory would have to know the social graph. However, sending search queries to your existing friends, by whatever method you use for updates, and forwarding them a couple hops might work nicely. No idea what they're thinking on this.
3) I thought I saw something about them using public-key crypto, and assumed they would be encrypting their posts with each friend's public key. Performance might be an issue, since they would have to re-encrypt for each friend, so maybe they are thinking to share a secret key with all friends.
It's true that you're trusting the host with your privacy that way, but instead of one big host that everybody has to trust, there are lots of hosts that compete with each other for people's trust. And there's no one place for marketers or other goons to find all the information on everybody.