Got final response from Microsoft Support: this is well-known issue with Server 2016 for about a year now. As Server 2016 is out of maintenance support, there will be no fix.
The issue is related to maximum character URL-limitation by OS.
Two possible workarounds:
- update to Server 2019
- disable SafeLinks Policy in Security AdminCenter (including exeption for BuiltIn-default-policy) and wait 24h
The issue propagates through all tenants starting about a year ago... so some organisations are affected for quite some time and some only recently.