I would argue that spam is an even bigger one.
Basically, the Internet has spam because identity isn't a limited resource. IP addresses are kind of a limited resource, but they're not really the property of the person using/abusing them, so a blacklist doesn't inflict precise targeted damage, can't be made too draconian, and is easy to evade in lots of ways.
And everything above the IP level is unlimited. If there's an unlimited supply of identities, you can't tell the difference between a new customer and an old enemy. You want the first to have positive default reputation and the second to have infinite negative reputation.
People in the personal cloud community often point to email as proof that spam can be solved. Yes - but spam was solved in email because email already existed in an spam-free Internet. On the Internet we have, there's a much easier solution to the fact that any new protocol which is successful starts to attract spammers. The solution is: stop using the protocol. Google turned off XMPP federation for this very reason.
Basically in an orc-infested environment, you can't have your own cute little bungalow in the cloud. You gotta have an apartment in a giant fortified castle in the cloud.
Having a limited supply of identities, in which identities are (a) property and (b) property you control cryptographically (Bitcoin style, "allodial title"), makes it easy to make spamming not pay, once the price of an identity is greater than the profit a spammer can earn by burning it. And it does not require a central governance authority, or even a central reputation authority. (Reputation authorities shouldn't be built into any system, because if they abuse their own reputations the consequences are insanely dire.)
NAT is a problem, but there are lots of ways to tunnel around it. Which all suck, of course, but...