It's a common problem on smaller forums. I used to mod on another forum, and the easiest way we found there was to require a new user's first 10 posts to be subject to moderator approval. It was tedious and a mild annoyance, and it didn't stop the spammers from posting, it just kept those posts from hitting the main boards. And since they needed a minimum of 10 approved posts, even if one cleverly snuck in (I noticed that sometimes they'd copy a post and sneak a link into the middle of it, so when scanning the posts in the queue, it would look legit), the majority never saw the light of day.
I like that idea, though the site would likely need more moderators (across the various language groups, too).