I know that certain google products automatically access Google's blacklist database. Can I do the same? Is there maybe a cleaned-up dns server against which I could verify my own dns queries? Or some Webservice I could use?
I have a linux firewall, so I can do almost anything programmatically.
To some extent, yes. Google opened up their malware blacklist by making the Safe Browsing API publicly available, and you can signup here.
That is, however, the only one I'm aware of them exposing to the public for free.