We have a small group of people we have banned and wanted to make sure didn't come back. We banned their accounts (duh

) then their IP's, cut back as far as we could cut without affecting anyone else who is a member, then I used the same IP's and denied them access to the website via .htaccess. Now when they try to access all they get is a 403 Forbidden error. (I may change that to something a little more clever at some point, but I haven't gotten around to it.

)
The drawbacks, as you've noted, are denying access to someone who should be able to access. In the last several months I've only had 1 person email me and tell me they were seeing the 403 error that should actually have had access. It was as simple as adding her IP to the .htaccess as allow and she had no problem after that. I was actually quite surprised, because we have almost 4000 members and we have been getting at least 10 new members a day over the last month or so. I make sure there is an email address on the 403 page so that if a legitimate user gets it they can contact me to help them out.
Unfortunately a big problem is AOL. We still have a LOT of people on AOL (maybe 50%?) and for the most part their IP's change so much there is no way you could block anyone without just blocking AOL. I know of several websites that have done this (I used to frequent Anandtech.com and they did this a couple years ago.) I'm sure a lot of people complained and they're right, it isn't fair, but it's also not fair to run a website and have to spend your entire day and night hunting and fighting trolls.

Since we can't really solve the problem with AOL'ers, we have the board set to require admin. approval for all new users. They sign up, I (and the other admin) get an email saying a new user registered, then we pull it up in the admin. panel. It has their IP and their email address they used. We faithfully run every IP through NeoTrace and see if it looks suspicious. If it happens to come from an area that we know one of our former trolls is in, we investigate it a little more closely before approving it.
When we were having a particularly bad time, we set up a new group called "New". We made all new users part of the "New" group instead of "Users", and set the "New" group to read only access to all of the forums. That gave us time to check them out a little more closely, see which forums they went to, what threads they were reading, etc. If they were hanging out in threads that a new user simply wouldn't have known existed (like a forum not seen to unregistered and a thread that was a month old) we knew they were digging up something, probably trying to cause trouble. Again, it warranted closer inspection. Sometimes I've even just sent the new person a PM telling them we are looking into some marketing strategies and it would be very helpful to know how they heard about our site and how they found us.
Yep, it sounds like a lot of work.

But it's at least kept the trolling down significantly.

Good luck!