The bans would not automatically extend to the whole subnet. Only the kick statistics, and only by default. If you have a static IP on a subnet with a dynamic IP bastard, you'll be immune to the bastard's evildoing. And if you don't get kicked at all, you're also immune. I think it would be a reasonable tradeoff.
Guess what we already do against attempts to turn over votes with 10 clients from the same machine?
The arrival time is already indirectly taken into account; the person online for longer always gets to keep his name.