* Don't delete ban accounts, don't notify them in any way, but tag their IPs and cookies to auto shadow-ban any sock puppets, so that these don't even make into an approval queue.
* Use heuristics to automate the approval process, e.g. if they looked around prior to registering, or if they took time to fill in the form, etc.
* Add a content filter for messages, including heuristics for an ASCII art as a first post, for example, and shadow-ban based on that.
* Hook it up to StopForumSpam to auto shadow-ban known spammers by email address / IP.
* Optionally, check for people coming from Tor and VPN IP, and act on that.
Basically, make it so that if they spam once, they will need both to change the IP and to clear the cookies to NOT be auto shadow-banned. You'd be surprised how effective this trivial tactic is.
All in all, the point is not to block trolls and tell them about it, but to block them quietly - to discourage and to frustrate.