Es verdad que no se puede guardar el resultado de un captcha como cookie, pero una vez aprobado el usuario (es decir, si ingresó el captcha correcto) se le puede devolver un cookie específico que funcione como alternativa al captcha. El cookie lo podemos ir rotando, tipo semanalmente, y como mucho cada dos semanas tenés que pasar el captcha. Creo que andaría bien y no sería muy molesto.