Why not just contact his ISP and inform them of his antics? It could work, I did the same thing twice when I was a mod on another board. The ISP's usually have a special E-Mail adress just for abuse issues. Of course he can get a new provider, but then you just fuck him again. It won't be long until he gives up.
But there's something else I don't get. When you ban one of his nicks, why don't you delete his posts as well? There are entire threads that are ruined because of his trolling. Just delete his posts, it's not like anyone will miss them.