Finally found a solution:
This problem happens only for a domain account (We use samba, win 10 and outlook 2016). The solution gives in
is:
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Cryptography\Protect\Providers\df9d8cd0-1501-11d1-8c7a-00c04fc297eb]
-> Add this key "ProtectionPolicy"=dword:00000001
The above register key solved my problem. Hope it is useful for others.
works with all newer 365 installs