Hello,
Why don't you block networks ??
Firewall - SYN Cookie enabling ?
What good is syn cookies against traffic that conform to tcp rules but are just too abusive?
Mail servers - use RBL list - this list will contain networks of IP's that belong to home users. So they do not need to connect directly to your mail server.
RBL does nothing against spammers who open 100 connections to each of your MXs and who run malware that do not understand,respect smtp 5xx. Dropping the connection means they keep coming at you. For these, there is nothing but a firewall that will keep them off your MXs.
Web servers -- rate limiting ? block networks ? Better web server ?
If you blocked networks ? The estimated max number of rules a packet might have to match would be 254 ... plus the rest of your filtering for ports and other needs. This could slow down network access because of all the rules to check for each packet.
If you are not using network addresses the list would become to long.
I am sure CIDRs were part of the OP's mind since iptables takes both individial ips and CIDRs. He probably does have a mixture of over a million ips/cidrs he wants to block.