I have that same no-permit permit. It was a rather amusing runaround to obtain, but every place that "needed" it was extremely lenient with timing. I found for every circular dependency, you could satisfy it by getting one element in the circle to accept a promise that the dependency that depends on them will be filled "later". Later can be months. It seems everyone dealing with the bureaucracy is used to it, and workarounds like these for seemingly impossible circular stuff are common.

You have this kind of insanity practically in every place with a bureaucrazy. It's not unique for Germany. You shouldn't worry too much, there's always a way around or through.