If new users are not allowed to post links until, say, their 20th or so post, and if they are not told so until after they attempt to do so for the first time,
1. they'll be surprised...
2. it'll cut down on the first-post spammers dramatically
3. it'll waste a little bit of a would-be spammer's time while (s)he sets up an account etc. only to be denied
Just a thought.