This is a really nice writeup, thanks Gregory. Such ideas have been kicked around informally for a while:
https://bitcointalk.org/index.php?topic=175156.msg1829259#msg1829259see the part about p2p mixing protocols ... but it's good to have a name and a formal writeup.
The examples of how ordinary, everyday privacy leaks can cause people problems are great. I think I've named the "people learning each others salaries" one before, but birth control is an interesting one.
I think adding a rendezvous mechanism to the P2P network makes sense. It's already a broadcast network after all. So perhaps the right design is not to try and do absolutely everything over the existing P2P network but rather allow people to announce rendezvous points (Tor hidden services?) over the broadcast channel and then allow nodes to set announcement filters like they set Bloom filters today. If you are an SPV/leaf node on the network you wouldn't hear announcements until you request them. Other nodes would relay them all.
The difficult part is that you need a lot of traffic to make this work. Current tx volumes don't even reach one per second. So to accumulate enough users for a mix, you'd need to wait a while. It's fine for some kinds of payments that aren't time sensitive, but it's not going to work today for restaurant bills.
If I were doing it, I'd want to do the bulk of the implementation in bitcoinj of course, just because that's what most users are going to end up using (given current trajectories). It also has the advantage that using a managed language like Java eliminates entire classes of security holes, always a concern when writing financial software.
The advanced crypto part isn't necessarily that advanced and doesn't require ZK proof systems. Such protocols were already designed:
http://blog.ezyang.com/2012/07/secure-multiparty-bitcoin-anonymization/It just requires secure multi-party sorts, which is a more well studied subset of general MPC.