no its not illegal, it just needs a lot of lawyers to workout the details. GDPR does not block a lot of things, it only requires you to work out the proper procedures and paperwork. And that is where Microsoft is good at, the compliance support.
I also wonder what the Schrems court rulings mean about US citizens working in the EU for EU companies, since the US might feel free to give purportedly binding surveillance orders to such citizens; or for EU residents who visit the US while working for EU companies and receive a binding surveillance order while in the US, possibly even with their work equipment and remote access to company PII.
If cutting out US vendors is disruptive, avoiding travel to and remote work from the US, and avoiding hiring (or being subject to hierarchical oversight from) US citizens in Europe would be even more so.
As a US citizen who is about to move to Europe myself, my preferred solution would of course be for the GDPR to be followed strictly and for the US to change its laws. But I'm really not expecting the US to pass that kind of legislation now.