Woohoo Jeff!

Tell me about it. This is actually a new type of spam you CANNOT protect yourself from. At least you are not going to get rid of it easy.

How it happens:
The account-signing process is accomplished by real humans, so email and image verification processes are by-passed without sweat. These accounts then submitted to a spam-generating script to play with.

How to prevent it:
You cannot stop it at source, banning email domains and IPs won't be effective as well. Here are a couple of things to help yourself. Since most of this spam generate new threads, create a permission that would allow users to create new threads only in the event of them having replied to other threads first. I had colleagues telling me it helped reduce the number of them.

If you run vBulletin, I came across this mod today (Mark of AvidInteractive actually pointed me to it):
http://www.vbulletin.org/forum/showthread.php?t=109258
It allows the system to analyze the post for certain words and send posts to recycle bin should the words of interest match with the content of a post.

Hope this gives a couple of ideas.