We had a big SEO spam problem with our forum, even with verified email addresses. I guess it is pretty easy to get a gmail address.
We fixed it by:
* moderating everyone's first post
* banning spam accounts liberally
* only allowing folks with a certain level of karma to post without moderation
* deleting any spam posts that sneak through, then warning or banning the poster
I think you need to spend some time managing your UGC.