I would argue that provable-identity is probably solvable in software, but that identity and utility are deeply connected notions. For instance Alice wants to talk to Bob to satisfy some want or need. His identity is only important to the extent that it is a necessary part of the utility of the communication.
Generally two nodes in a network can prove that they have access to a particular set of keys, but the system tends to fall down on proving that they are useful to each other. A MITM attack is merely one party pretending to be as useful to the communicator as the intended recipient. If you disagree consider that your packets don't go directly to your bank, but are "rebroadcast" by routers and switches along the route.
But how do you know that Bob exists and you want to talk to him? At some point you met someone named Bob and at some point you decided you wanted to communicate with him, but Bob as an identity really only exists in your head. He could be named Jim, he could be someone that is pretending to be Bob, Bob might be one of two twins both named Bob. Maybe Bob is working for your enemies.
One way to simplify the thorny issue of identity is to look at what someone wants out of the communication. The part of the identity Bob that matters to a communication is the expected utility of the communication. The identity is merely an end to that utility. For instance when you call tech support, you are trying to solve a problem and it doesn't really matter if the person tells you their name is Jim rather than James.
The only hard and fast identity is cryptographic identity, it can be compromised if someone shares their secret key, but at least you know that you are communicating with someone that has access to that secret key. That is, I can send to a message to all parties with access to the secret key, SK0. The next question is how do I know that parties which have access to SK0 will increase my utility via communication. That can only be built from past actions either directly or indirectly performed by that party.
Utility of identity depends on reputation of identity. Reputation of identity depends on past actions of identity (think stackoverflow/hackernews/silkroad).
All of which can be cryptographically proved if the identity consists merely of access to SK0. Note, this is how identity and trust works outside of computers.
The reputation system tied to that identity could also be compromised, the difference is I'm much less likely to find out until it's too late and the potential harm to me is very high (lets say the government is operating a Silk Road honeypot). That brings us back around to the problem of identity. If I know and trust Bob then his utility is higher.
Which is the point of the "web of trust", it (sort of) builds that utility system in. I personally know Bob and know he's pretty sharp. He knows Jim and has signed Jim's key, but I don't know Jim and I'm taking Bob's word for his identity. Jim knows someone as well and has signed their key, but now we're getting pretty far removed from Bob. Their utility (in this case their utility at confirming identities) is getting smaller for me. I'm less inclined to trust them.
But Bob, Bob's an old friend.
So I see where you're going, but I still think "identity" is the critical factor.
Agreed. So how do we live in such a world and make decisions?
Do you trust Bobs ability to protect his key? Can you buy insurance against this given Bobs reputation? Are the premiums worth the cost?
So I would say that you can reflow communication all you want, but that the underlying problem here is trust and knowledge and those are social problems. People either need to appreciate what these new communication flows mean and/or establish ways to bring their communications under their control (i.e. crypto).
That said, I think the idea of establishing trust through key signing parties (and "crypto" parties) is an interesting one. One of the key features of this is learning from someone you likely don't know, just as when you do a key signing party everyone requires some sort of government ID. In the end, you've got to put your trust in someone, right? So, back to the social problem.