I knew about this part of the law too, and it sounds like captchas don't count as "strictly necessary" based on the original part and the Opinion 04/2012 on Cookie Consent Exemption you linked, but I'm not sure.

"Simply using a cookie to assist, speed up or regulate the transmission of a communication over an electronic communications network is not sufficient. The transmission of the communication must not be possible without the use of the cookie." - criterion A "A cookie is necessary to provide a specific functionality to the user (or subscriber): if cookies are disabled, the functionality will not be available." - B

For B, they say for example that a session ID to keep a user logged in is fair to use without asking, provided the user explicitly wanted to log in.