A lot of those have a wide range of entries, so they do seem like spammers. Otherwise, it's really hard to say. It may certainly not be "all" users, but it definitely looks like your anti-spam settings were set very tight (reject on 1 flag requiring 1 or more sightings; the default for rejection is 3 flags requiring 5+ sightings).
Spam phrases are really the most you can do, unless you want to start identifying unique IP ranges they use and banning large swathes. You would need to identify words they use that others don't and then block their posts.
Or move to a system where you moderate initial posts.
You are moderating them. That means when a new user posts, you determine if they are a spammer or not. If they are not, once you have moderated 5 posts (or whatever limit you set) they will be free to post without moderation. If you do determine that they are a spammer, you don't approve the posts and you ban the spammer/delete the account etc. They won't get email newsletters sent to them.
It doesn't stop them from signing up, no. The spammers you're seeing are likely humans (despite how their messages may look), so there's only so much you can do to pre-emptively stop them from registering.