For all you guys stumbling upon the same issue.
This did the trick for us.
Since we were providing access to the WHOLE tenant and not just a site or sitecollection we needed to set the permissions on the tenant-admin-url
Literally the passage:
So what changed? Well, ...