Skype for Business 2016 prompting for Duo every time

We are rolling out Duo by protecting our ADFS logins. Our users use Skype for Business 2016. Some, but not all, of our users are getting prompted to authenticate with Duo every time they start Skype in the morning. Other users were prompted once and never again, which is what we want.

For the users experiencing this issue we have:

  • Signed out of Skype for Business and deleted Sign in Info
  • Removed all Windows cached credentials
  • Uninstalled Office and reinstalled

For some users, the first item fixed the issue. However we still have users that are prompted every time. Any ideas on how to fix this?