So you would have potentially huge overhead bandwidth (99 clients download my files just to test to /dev/null and the 100th actually really needs the data) - good for anonymity ("I didn't need the part, my client just loaded it randomly to check!") but really bad if I want to host 5 TB of data with 1 MB chunks:
1 download of 1 MB per week(!) would mean:
(5*1000*1000)/(7*24*60*60) = >8 MB per second constant upload only for making sure the files I claim to store are actually available. If more than 1 client actually wants to check 1 piece (I'd want to have estimates of at least a handful of clients how trustworthy this random storage node is in their experience) you'd even have to multiply that, so a 100MBit line isn't even enough just to make the data available.
This will definitely NOT be "dirt cheap"!
Also you (or NCs) have to trust other clients - then you can trust the storage node itself too, because for all you know the operator of a storage node could also operate lots of sock puppet client nodes that praise him for his great reliability.
You don't check every chunk by downloading, only small portion. Most chunks would be checked using salted checksum method.
Also, this was never intended to be a 1 Client : 1 Node. What you want to do is to put your data onto as many nodes as possible. This way, if needed, you could download all of it fast, even when individual nodes have suboptimal uplink.
Regarding sock puppet nodes - you can probably do that. I imagine, the nodes that do that would run into the problem of cost associated with running that network. I would also imagine, client would be able to blacklist node by ID or IP address, so if there is a known scammer, it will soon run out of paying clients.
And would it put a strain on node's network and other resources? Hell yeah. But so does bitcoin client, skype, tor node, freenet node, bittorrent client. If it was no cost, why would anybody pay for it.