Hi @Matthew Beck - thanks for your question.
It's possible that your users are hitting one of the scenarios covered by https://learn.microsoft.com/en-us/outlook/troubleshoot/authentication/outlook-prompt-password-modern-authentication-enabled (basically, related to having migrated from an on-prem Exchange to M365).
Can you take a look at that and see if that helps?
----
If this helps, please remember to upvote and mark as answer so that others can find the solution in future.