I really dislike CAPTCHAs. They don't work. They simply annoy the human user, prevent some colour blind users from posting and just encourage robots to try and re-try (xN) until they get their comment spam through.
The funny thing is that Ian McAllister blogged about the very same annoyance recently.
Never in the history of Search has any engine been so up front as to actually prove the impact of a link or attribute. This seems like a hard circle to break.
LiveJournal (which is now back to using ads) may have a simple solution in the community front. You can lock you blog down to comments only from friends. People who you've approved don't need to deal with CAPTCHAs and spiders simply cannot post. LiveJournal also "nofollows" the entire "Friends" page side of every blog and community there.
The problem with the friends/community front is how you get into the loop in the first place. If you cannot comment on a blog then you'll not be able to announce yourself as a reader to the blogger. If you can't do that then the blogger can't add you as a friend.
What would really turn comment spam off is if 'rel="nofollow"' was seen to work. Right now there's no incentive for spam bots to detect and avoid these blogs. Its much easier just to flood many blogs at once.
My radical solution is to charge people a deposit whenever they comment on your blog. This solution only becomes possible when micro-payments are possible (we're waiting on PayPal or Google's payment system in Google Base to give that to us). Each blog comment leaves a deposit of 1p (or there abouts) which is refunded by the blogger when the comment is approved. Alternatively, the deposit auto-refunds a week later unless that's overridden by the blogger. Actual users are never really exposed to any real financial risk. Spam bots with tens of thousands of comments certainly are. The draw backs? This system faces the same challenge as PayPal does. You may need a credit card in order to get into the loop in the first place.