Must block contents be stored with the proof that they haven't been changed? The replication of the block contents across all full nodes has been bothering me for some time.  Isn't the header of a block enough for me to validate the block contents if and when I get them (which I wouldn't until something told me that I need that block)?  When I get blocks, I can save them, but I suspect there are a large number of blocks I don't need.  I'd be willing to pay a small fee to get a block from someone else if that means I get an extra 20 GB on my hard drive indefinitely.

I guess this is a bit like an SPV client, but I have seen no middle ground, where a client has a bunch of seemingly random blocks (but they aren't random - they contain all the transactions required to prove the current holdings of the person running it).  If such a client existed, it could hold and update the UTXO set as each new block comes in, all block headers, blocks important to the operator's acquaintances, and blocks the operator thinks might be valuable.

If we are trusting the network to provide the hashing power that prevents changes to the data in the blockchain, can't we also trust the network to provide the data itself?  Hashpower is valuable right now because of A) the subsidy, and B) transaction fees.  It makes sense to me that storage space is also valuable.  But while transaction fees are generally designed to cover that cost, they are allocated to hashpower rather than those providing storage.

Finally, if I had the complete UTXO set as of some previous block, and I've watched all the changes to it represented by all the blocks since (without necessarily permanently storing them), then I can determine whether or not any incoming transaction is valid.  I think the storage requirements for a client that does this are well under 10% of the storage requirements of a full node right now.

Am I missing something?
Sounds like you are describing a pruned node. As of Bitcoin Core 0.11, you can run it with the experimental -prune=N option, which only keeps the last N megabytes (min 550) worth of blocks, plus the UTXO set. In 0.11 it is only useful for some RPC commands and mining, but it disables the wallet due to being too experimental. In 0.12 the wallet function will be available in pruned mode.

All blocks and headers are still downloaded and validated fully, but the old blocks are deleted from disk occasionally.

Also, I think it is a bit incorrect to say that hashing power prevents modification of the block chain. Block chains are by means of hashing always immutable and only append-only. However, in the presence of multiple valid competing block chains, most hash power decides which one is to he accepted.