This could be implemented by requiring users to have enough CAPTCHA tokens to perform an op. Witnesses, or other CAPTCHA providers could broadcast a custom_json op whenever someone solves a CAPTCHA, and witnesses would ignore transactions that would cause someone to have a negative CAPTCHA token balance. This would not require a hard fork, and could be implemented immediately.