We are having an issue with a recent office 2021 update where mailboxes with granular user permissions no longer fast search even with 'Download shared folders' switched off.
The only way we have seen that this is 'resolved' is by applying the 'FullAccess' permission in exchange to the mailbox for the user. We do not want this because users for these mailboxes should only be read access. Have tried adding 'ReadPermission', no result.
If you force to 'Current folder' and search it says 'Cannot display the folder'. Still no problem with office 2010 or outlook web for searching in this configuration.