That's your problem right there. If you live in Berlin, take the 2 hours and go to Hamburg or Leipzig before doing anything that needs a working bureaucracy.
[ed.: a tiny office in Leipzig is pretty cheap too, but you'd need to ensure mail doesn't pile up there unchecked.]
Unfortunately I'm not joking about this entire thing. Berlin's underfunded, overstressed bureaucracy is to be avoided like the plague.
[ed.2: to be clear, it'll still not be great. Just less bad.]
But also, yes, this is one of the reasons you can hire lawyer's offices to do this, they know how to spin it such that they're regarded as administrating the company in their location (which is arguably true at that point).
And just to note, there's the concept of "field offices" (Betriebsstätte) which would need to be set up. That does still involve Berlin bureaucracy, but only for a Gewerbeanmeldung.
(Really: ask a lawyer. I hope nobody is taking legal advice from a HN thread.)
Again this is very straightforward and routine in the UK: https://paramountformations.com/product-category/off-the-she... ; a similar experience to buying a domain and spinning up a website on it. In organizations like investment banks they will have shells ready to go in the way you would have kubernetes pods.
So, the story is really that it takes a couple of weeks for a freshly founded company to be ready to invoice customers outside of Germany, which I agree, is a sad state.