I really hope you can avoid the nightmare that is manual user validation. It would absolutely eliminate the spam, but it's really tedious and time consuming, and it's not user friendly.

Another option would be to enable post moderation for a new users first few posts. That wouldn't actually stop the spam, but it would keep it from showing up on the board. I don't really think clicking the links is an issue, but it would improve appearance at least. I'm not sure how vB handles post count and moderation (does an unapproved post count toward the posts needed to get out of post moderation?). That would be less time consuming than manual user validation, but still annoying. Hopefully using the questions takes care of it.