Problem was, that rsyslog was sent all messages (including the logged DNS requests) to the Graylog-server. And the Graylog-Server try to check the IP against the DNS and so on.
I solved it, by exclude the named (ISC bind) and unbound log entrys. Since they will not be sent to the Graylog-Server, everything was as expected:
DISABLE -->
Force rDNS resolution of hostname? Use if hostname cannot be parsed. (Be careful if you are sending DNS logs into this input because it can cause a feedback loop.)