I think Joe Cascio's idea of "collateralized identity" looks really interesting here:
The core problem we're really trying to solve with a CAPTCHA is: anonymous identities are very cheap to create. We can require the user to provide and verify an email address, but it turns out those are cheap to create too. What we really need is a way for the user to prove that they have something invested in their identity - be it monetary value, time, cpu cycles, or whatever. A bit like slashdot karma (so you can filter out trolls/spammers using identities with nothing invested in them, which are cheaply created/replaced.)
Bitcoin, if it should ever gain widespread adoption, provides a very convenient mechanism to accomplish this:
1. each bitcoin user already owns pseudonymous unique public identifier (ie. their bitcoin address), which they can provide to any website as a portable identity
2. to prove ownership of this identity the user can sign a challenge from the website using their private key (hey, we just solved the password problem too!)
3. an amount of monetary value (ie. bitcoin) stored at this address, plus the length of time it has been stored there, is publicly visible on the block chain.
This allows the website to assign weight to the identity based on a combination of: the amount of value stored with the identity + the time it has been stored there. An identity that has had $20 stored with it for 3 days is probably not a spammer. An identity that has had $0.20 stored with it for 3 months is also probably not a spammer.
Of course it is easy to generate an unlimited number of such identities - but hard to have a decent amount of value stored with each of them for a decent amount of time. Websites can easily adjust the weighting threshold required to sign up / post comments based on experience with incoming spam. And there's always the ban hammer - which suddenly has some real weight behind it again
Important to note:
1. the money (ie. bitcoin) associated with the ID stays under the user's control at all times. The user alone has the private keys required to transfer/spend it any time they like - of course doing so would lower the weight assigned to their identity by any websites that inspect it.
2. the website need not store any authentication information for the user (eg. a password). The user retains control of their private key, and can use it to authenticate without disclosing it to the website.
Too hard for Joe Public to understand? Maybe.
Just imagine this all wrapped up in a friendly browser plugin. When you visit a website there's no login page - your browser has your private keys (perhaps encrypted with a master password, like Firefox's password manager does today) and just automatically authenticates you. Your browser could provide a drop-down "switch identity" widget in the toolbar to let you flip between multiple IDs / generate new ones, which is the only bit visible to the user (they need never hear terms like "private key".)
An "add weight to this identity" option would allow you to add/withdraw funds for any ID. Initially this might look like a bitcoin transfer (confusing for non-technical people), but a private company could easily provide a regular payment gateway on top of this (ie. accepting dollars), making the process no harder than recharging your skype credit.
Adding weight to any identity would be strictly optional, but might eg:
* allow you to skip CAPTCHAs
* allow you to post at +2 on slashdot by default
* generally increase the trust in your identity being genuine all over the web - use your imagination....