Mi pare strano riuscire a far meglio di iptables, comunque hai scartato a priori l'uso di una hashtable e di una funzione di hash general purpose?
Ti dico subito che scomporre i blocchi (se ho capito cosa intendi) non funziona, perché potresti avere falsi positivi.
inserisci 1.2.3.4
inserisci 5.6.7.8
hai come falso positivo: 5.6.3.4 che non hai mai visto.
Se conosci in anticipo il range di IP da bloccare potresti tentare di fare una perfect hash function.
Oppure usi un bloom filter:
https://en.wikipedia.org/wiki/Bloom_filter
Il vantaggio è che è molto compatto (nell'ordine di centinaia di kilobytes se usi k=8 funzioni hash a 20bit), lo svantaggio è che è probabilistico e va dimensionato correttamente.
Se riesci a tenere tutto nella cache del processore è abbastanza veloce.