CAPTCHA is broken and, at least in my experience, does more to harm legitimate users than inconvenience bot makers. You can farm out CAPTCHA solving to China for less than $1 per thousand solved.

When we installed it, spam users registered dropped to zero. I think its very secure against undirected attacks,

Totally agree. Bots vs humans is not an issue of security at all in a cryptographic sense (which that phrase refers to). For this particular task all we have are tricks that have practical value. It isn't even clear if the problem is meaningful in an absolute sense, while cryptographic protocols can be clearly defined and reasoned about.

Would it even be possible to solve this problem in a serious way? If you could then would that mean strong AI is not possible? If not then why don't we figure out something better like asking users to actually pay for things and then we don't have to solve these philosophical quandaries. If it's too hard for people to pay for things then lets focus on that problem instead. If you don't want money and just want to rate limit then look into proof of work puzzles.