I wondered if it would be possible to use something like Hashcash to require a certain level of CPU usage from the user agent? It doesn't stop spam, but it's unobtrusive to the user and would slow spammers down.

http://en.wikipedia.org/wiki/Hashcash