These ideas are drawn in large part from Stack Exchange and partly from anti-spam techniques.
Filtering
If there are patterns in the trolling, you could take a page from automated anti-spam measures and apply pattern-matching to the problem. This depends on how well you can characterize trolling messages, of course; start building a corpus. There may be low-hanging fruit like certain words.
Because any filtering system is imperfect, you probably want to queue these messages for human review rather than just dropping them on the floor. False positives are thus delayed in posting but aren't lost entirely, which is important in not alienating your legitimate users.
Learning
You have useful data in your existing posts: you know which ones were valuable versus not and what IPs they came from. Maybe you can leverage that.
Instead of just blocking IPs because a troll used them, you could check the history for that IP. Gee, 37 posts with a total score of +719 came in this week from there, plus three troll posts? Maybe you don't want to block that. 12 troll posts and not a single good one? That'd be safer to block. (Note: to do this, you'll need to keep track of the reasons you delete posts.)
Hobbling
If you're getting trolling from certain IPs but you also have, or might have, legitimate users there (who can't register for some reason), another approach you can take is to hobble instead of outright blocking. One way to do that (used by Stack Exchange at the user level) is to limit the number of posts that can be made in a given timeframe. Good posts (however your community defines "good") should lift the source out of the hobbling; meanwhile, at least you're cutting down on the flood. A similar approach is to hobble performance (pages just load more slowly, etc).
Scope
Applying any of these measures runs the risk of aggravating your legitimate users who happen to share IP space with the trolls. A good way to mitigate that is to only restrict anonymous users. If a registered user starts trolling, I presume you have other ways to deal with that.