Seems like, if you detect a bot, you should impose a captcha on every x actions. Not enough to ruin your customer's experience, but enough to make botting harder.
- captcha that isn't hard for humans is often easy to automate
- captcha that is hard to automate frustrates a lot of humans too
- and to add insult to injury you can "automate" the hard ones too by paying like $1 per 1000 captchas or something (think Amazon Turk like stuff)