SSO Licensing doesen't Work every Time

Hello everbody! 

I'm dealing with a strange problem at the moment. We have Terminalservers 2016 that want to Access the installed O365. 

Regular, they open an O365 Application like Word, and then getting an License over SSO. At the moment we get more and more Users how at the "Sign in" Screen when they open an O365 Application the first Time in the Session. 

We have Users they have to login every week, at other users (Same Terminalserver) there is no problem.

Things getting stranger, because now in some cases also logging in, in the "Sign-In" page dosent help. You have to do this multiple times befor the get an Licence.

There are enough Licenses the whole Time. And if i try SSO by opening the folloing Link. It Works perfect! https://myapps.microsoft.com/mycompany.onmicrosoft.com 

Do any of you have a plan, how i can solve this problem? 

Regards Tom