I can now report, that I re-submitted and validation went through within 10 min 
The key difference in my submission was, that the first time around I submitted our DUNS number in the validation form, assuming that that would make things easier than submitting a German Tax ID, as the DUNS can easily be verified online and Apple uses that to verify, too.
This time I submitted our German VAT ID in the validation form and 10 minutes later my validation status went to status “Completed”. (They did however fix part of the input field restrictions that I mentioned on my github issue, so street address numbers now also take forward slashes like “12/3”, which they didn’t last time I tried).
So all in all it really seems like Microsoft support is on top of it and it’s just hiccups happening.
//Edit: About 1h of fiddling with our CI and I have Trusted Signing fully integrated in bash on Windows.
In case someone is looking for the magic lines that make all this work unattended:
az login --service-principal -u "$AZURE_CLIENT_ID" -p "$AZURE_CLIENT_SECRET" --tenant "$AZURE_TENANT_ID"
signtool.exe sign -v -debug -fd SHA256 -tr "http://timestamp.acs.microsoft.com" -td SHA256 -dlib "$ACS_DLIB" -dmdf "$ACS_JSON" "$path_to_your_file"
az logout