I should have mentioned that I've running Pi-hole behind a lighttpd reverse proxy.
After further debugging it turned out that lighttpd by default do not allow „percent-encoded control characters“ in the URI and returnes the 400 error.
The solution was to add the following to my reverse proxy config:
server.http-parseopts = ( "url-ctrls-reject" => "disable", "url-path-2f-decode" => "disable" )