The problem with using a hashcash style spam-prevention is that it almost has the opposite effect on a distributed network. One user who can make 1,440 transactions per day can have the networks bandwidth multiplied by 1,440 txes X the number of network peers. "It shows work! I must pass it on to everyone I know!" Multiply this by a botnet and you have complete network collapse. In addition, providing a nonce as proof of work with each transaction will increase the size of each transaction by at least 32 bytes, perhaps 64 bytes or more. That is a significant increase in bandwidth to avoid paying transaction fees. Proof of work as tx fees is more easily DDoS'd and less scalable.