Finally found the solution: It seems to work, if the taxonomy is registered in the blog, where we’re doing our query. E.g.:
Im working in Blog 1, querying posts from Blog 2. The Taxonomy XY exists in Blog 2, but not in Blog 1. Once i add it to Blog 1, the Query works.
Hope this helps somebody.
For the search engines:
“Invalid Taxonomy”