Also, since the OP said the spam was from accounts just created, you could add a third threshold (time since account creation before you can submit a story).
By the way there is no reason to pick these thresholds out of thin air - presumably one can look at say the karma distribution of link submitters and figure out what the highest threshold that would inconvenience the least number of people is. For example, I would be truly surprised if 95% of stories were not submitted by people with a karma of 5 or more.
Instead of a captcha, what about something that is like a puzzle to complete, that way you can also avoid low quality submissions which might come from people not intelligent enough to solve said puzzles and would also be a delightful little game for the rest of us who like to solve puzzles/problems?
First, I don't think I would be delighted by an automated puzzle on HN.
Second, the idea that puzzle-solving-ability is somehow closely related to interesting/insightful writing is specious. People are smart in different ways, and as a programmer myself, the kind of smart that I want most is the kind I don't have, which is often not the problem-solving kind.
All that having been said, I'm not against a captcha. I just don't think it'd be delightful and I don't believe that it'd somehow raise the quality of posts around here (beyond from removing some spam).
I am not against a captcha level puzzle ("which box is blue") or arrange these numbers in order of least to greatest. But to do so to limit "less intelligent" members amounts to censorship and I cannot support it. The goal it stop spammers mechanically, and allow normal people to post, whether their post is of substance or not.
