> The street address/book scan approach that Google uses is interesting in that the exact solution is not known, so they presumably have to be somewhat forgiving in accepting answers

reCAPTCHA presents a known problem and an unknown problem to the user. If the user answers the known one correctly, it assumes that the answer to the unknown problem is correct too. I believe the text-based reCAPTCHAs will accept an answer within a character or two as correct.