You may want to take a look at hashcash[1]. It was a proof of work scheme for email invented in the late 90s, and they claim it was adopted by bitcoin[2]. (Sadly, it never caught on for its 'intended' purpose.)

[1]: http://www.hashcash.org/ [2]: http://www.hashcash.org/bitcoin/