I don't know if spam is more annoying than how this discussion turned out.
For you, maybe not. For most users, definitely yes.
I spent several years running some of the most contentious forums on CompuServe, so I'm intimately familiar with the frustration and annoyance of complaints from users who often don't understand how difficult it is to keep things running smoothly. Which, compared to a huge number of forums on the web these days, you do quite well (anybody who thinks the spam problem is bad around here should spend a few hours reading some unmoderated Yahoo groups).
Even though it sucks that you're not getting much explicit praise for keeping this place chugging along, you should take encouragement from, and pride in, the fact that so many people are voting with their electronic feet by coming here every day and using it. You shouldn't ignore the occasional complaint, but I would encourage you to look at the stats on the number of visitors and postings to help keep the complaints in perspective.
Any forum will get spam unless they make life very difficult for legitimate users.
True, but you can dramatically cut it by making it only slightly difficult for legit users. The "No links in your first posting" limit is a good example: expanding that to, say, the first 3-5 postings, and adding a daily posting quota for a brief trial period, would take a big bite out of spamming with only a minimal inconvenience to legitimate users. The quota should run for a short time (2-3 days) from the date of first posting, not the date of sign-up, to keep spammers from setting up accounts and waiting out the quota period before unleashing a flood.
I'd be happy to discuss this idea in more detail if you let me know it's feasible to implement it (i.e., that there's someone who's willing, and has the time, to do the tweaks to the YaBB source and/or config files).
Two final thoughts: the vast majority of users will put up with the occasional spam attack or other misbehavior if they perceive that problems are being addressed. When spam postings hang around for days (as happened with the "counterfeit shoe" spammer), and the posters are not seen to have been whacked, user frustration builds. Moving to add some more moderators should be a big help. It will probably also help to occasionally make some sort of public announcement about what's been done lately to suppress the spam. Let people know that they can contact one of the moderators, who will make the spam and the spammer go away quickly, and they'll see it as a minor cost of free speech, instead of a major imposition.
As I said above, you've built a damned good resource here, that a huge number of people prove every day they consider very valuable. Don't be discouraged by the rare complaints.
Ran