Yes there have been various attempts at proof-of-work algorithms to fight e.g. spam. http://en.wikipedia.org/wiki/Proof-of-work_system

Bitcoin is itself a proof-of-work system.

However, these again don't work. The abuser has ample resources to actually do the work on: a botnet.