[AngelBlue]

Here's how I combat this problem on my forum:
* Use Multiple Account Registration Prevention, so when they sign up for alts, the alts are put in a usergroup without posting rights.
* Use Proxy to Real IP Conversion
* Setup a promotion system such that when someone gets -5 reputation (or -10, or whatever) they're moved into a usergroup which makes all their posts moderated. Then encourage members to moderate them.
* Use the 'miserable users' plugin to make them think your server is sucking, but they are not banned, so they never bother trying to evade the ban. If you're really evil, combine this with Multi-Account Registration Prevention. Set it to use cookies only, and put new accounts they register into a group with limited posting rights and to which the miserable users plugin also applies.
* Limit the abilities that new accounts have, so you can catch alts before they cause major damage.

I haven't used it myself, but you might also want to try :
* banning by cookies
* Use the community-driven moderation system (I forget the url, it is on vb.org somewhere)
* If your users don't know about cookies, disable the "log-out" button so once their account is banned, they can't logout. WARNING: they may clear all cookies to get around this, and this will prevent above steps from working.

Also, if you gave us more detail about exactly what they are doing to be a pain in the ass, that would help.