Yeah, the current scheme is not very super and will be biased to some items depending on the existing random distribution. A nice queue with proper expiration and refreshing would be better.

There are 10,000 captchas, so coincidences are likely after ~sqrt(10000) = 100 attempts. That's not a break in itself, the break comes if the attacker is able to manually solve say 100 captchas, and then do a brute force attack with a success rate of 1%. But an OCR method may well give a better hit rate, so it might not be worth all that human effort to build the dictionary. A manually-constructed dictionary can easily be invalidated by regenerating the captchas, but an OCR method would require a change to the algorithm.

Changed title, the problem is the challenge set size, not the randomness. It's perfectly random.

Not a MediaWiki, but a Wikimedia issue in FancyCaptcha images generation, and possibly a superseded one if Aaron produced the last set with a bigger dictionary. Aaron?

Aaron: Could you answer comment 4 please?

There is an option in confirmedit ($wgCaptchaDeleteOnSolve) to delete the captchas after they are used. See bug 24730.