Is there any similarities in their identd? How about address? I cant see doing an effective ban on nicknames as eventually you'll ban everybody. Maybe try to find some patterns in the nicknames or channel they're in to ban them with too.

Those who fail history are doomed to repeat it