Curious_One may have an idea here. Use the things that should uniquely identify someone to enforce a ban. I know what everyone will say, that it is easy to get another email address or IM handle, but I was thinking along the lines of what companies like eBay try to do.

A long time ago when you signed up for an eBay account they would require some sort of "proof of identity" if a person tried to sign up with an email address from hotmail or yahoo or something like that. Maybe there is a way to screen for these types of free email addresses and make someone that wants to sign up with one somehow verify who they are.