I can think of two solutions:
1.) Look into adding the bantron mod
to your forums. It will let you better control who is banned. When your problem users come back to sign up a new username, make note of the IP address that they came from and/or what email address they used when registering. Then, use Bantron to block that IP address and/or emaill address permanently.
2.) Change the verification setting from User Verified to Admin verified. That way you'll be able to approve user accounts before they ever show up on the board. If this is too cumbersom, at least enable user verification so that they have to have a valid email address.
Good luck. Let us know how you make out.