(1) Every NAT traversal protocol is unique, so there is no interoperability between different apps. The power of IP lies in the fact that it's a lingua franca-- anything can open TCP or send UDP. But anything cannot speak BitTorrent-DHT or Skype or whatever. So there's no potential for exponential growth in capability by tying disparate things together. Firewalls and NAT kill protocol interoperability.
(2) NAT traversal is hard. I know cause I just did it. It's a pain in the rear, and I'm still going to have to build port 80 HTTP tunneling into ZeroTier for that 0.1% of users who cannot use UDP or tunnel through their NAT. So you have to implement NAT-t + a proxy service for everything.
As far as spam goes, you're right. I should have mentioned that. But there are lots of strategies for dealing with spam. Why can't we have a few million small castles instead of one big one, for example? BBSes each had sysops who would kick off abusive users. There are also cryptographic things like hash-cash, Bitcoin economies, trust matrices, etc. These are complex but if we could engineer something good here then it could eventually be packaged into a friendly library that programmers could use without having to understand all the devilish details.
The fact is that we did build a decentralized many-to-many Internet. Then we broke it with firewalls and NAT.