Do they use Auto-Mapped mailboxes?

 Had this issue with a number of staff here directly after migration from 2010 to 2016

Fix:

$mailboxes = Get-MailboxPermission -Identity * -User <username> | Select -ExpandProperty Identity

Foreach($mailbox in $mailboxes){Remove-MailboxPermission -Identity $mailbox -user <username> -AccessRights fullaccess -Confirm:$False}

Foreach($mailbox in $mailboxes){Add-MailboxPermission -Identity $mailbox -User <username> -AccessRights fullaccess -AutoMapping $false -Confirm:$False}

Wait a few mins then see if the user can open Outlook.