My server uses SpamAssassin to detect if incoming mail is Spam. One of SpamAssassin's capabilities is using real-time blacklists (RBL) to check if an IP address is known to send spam mail.
Unfortunately, this did not work. E-Mails delivered to me contained the following header:
X-Spam-Status: ... tests=URIBL_BLOCKED
The URIBL about page tells us when someone gets blocked:
If you abuse it, we will block your IP, or your nameserver IP that is producing the excessive queries.
...
If you use your ISP Nameservers for resolution, and they are blocked, consider running your own caching nameserver.
And this was my problem: I used Hosteurope's DNS server - just like thousands of other servers running in their data center - and many of them tried to use the URIBL.
Testing
It is easy to verify if you are blocked:
$ host -tA 2.0.0.127.multi.uribl.com
2.0.0.127.multi.uribl.com has address 127.0.0.1
If you get 127.0.0.1 as response, then your name server is blocked.
More information:
$ host -tTXT 2.0.0.127.multi.uribl.com 2.0.0.127.multi.uribl.com descriptive text "127.0.0.1 -> Query Refused. See http://uribl.com/refused.shtml for more information [Your DNS IP: 62.138.131.21]"
Own DNS server
So I had to run my own caching DNS server on my server, listening on 127.0.0.1.
dnscache
Because I already use DJB tinydns as name server for our own domains (and DynDNS), I tried dnscache from the same package.
After successful setup I tested a bit and found out that it has at least one bug: It could not resolve barcelona.de, while this was no problem for all other servers I queried.
The djbdns tools have not seen any official updates since a decade, and dnscache is unusable now.
Unbound
The light-weight alternative to Bind is Unbound.
It is available in the Debian package repository and quickly setup without any problems.
After setup I only had to change my server's /etc/resolv.conf to query 127.0.0.1, and that's it.
The URIBL_BLOCKED messages are gone.