It's not so much that Office 365 is illegal as much as it is the storing of GDPR sensitive data in it (ie PII of customers and/or employees) because the German government does not trust Microsoft to not share the data with US spy agencies. (And does not trust the US spy agencies to not share sensitive data with other strategically interesting US companies. America First and all that.)