Most DNS blacklists have some DNS zone-interface, too. For example, if 44.33.22.11.this.dns.blacklist.com resolves to 127.0.0.2, that means this IP is blacklisted. This check is fast, mostly because it uses only a simple UDP send/receive, and because its result will be cached automatically by your local caching dns server. This feature is always well documented on the site of the blacklists.
It could be made more faster, if you find a way to make this blacklist lookup parallel, although it were not easy in php.