A possibility is to allow the users yourself, manually. The problem is that some may register to post immediatly, and if they can't, they may never come back...
Also what happened to me on a messagboard is that the admin obviously forgot to activate my account...
You may give some of us the rank of "spam moderator" if you will. There's some spam, but not like 100 a day... So if several are made moderator, it'll be clean regularly. When I say moderator, I mean only to clean the spam, not to start appreciating posts, closing and merging threads and things like that...
Some of us have been around here for a while, and I don't remember any flamewar or whatever that could result in moderator power abuse...
But maybe you prefere to ban the IP adress for each spammer that registers and as such prefere to do it yourself.
I've also seen some word censors, that rather than transform a word in another one ask you to change it before posting, so anythign sex or drugs related -well, at least drugs related- can't be posted
I also thought making it mandatory to have an avatar could help, seeing how spam bots never have one, but some people don't know how to upload an avatar, sooo...