Sounds like you got a lot of people that need to either
A) clean their computers and install some valid antivirus/malware protection and USE it
B) Practice safe hex
C) contact their ISP to get those IP's cleaned up (unless it's a static IP and then they may be able to)
Or you can
D) Disable all spam prevention measures and become spam haven and kill yourself on keeping the system clean
I'm using Tenant's add-ons, but I think it's in the ACP -> Home -> User Registration on 1.1.5. Make sure that Check DNSBL on registration is not checked.
If checked, you could also just check the box for require the registration to manually be approved by an Admin and have them contact you through the Contact Us option on the forum.
Curios, but do you use CloudFlare (or something similar)? If they are not in your IP list of banned IP's then there is either an add-on blocking them (and not necessarily in the xenForo software - I'm thinking of something like zBBlock) or you have a service installed on the front end that blocks.