Outlook in Cached mode uses LOCAL indexing for searches. Outlook in Online mode, or OWA, or ActiveSync all use Exchange's indexing service.
Which mode are they using?
You can also try the following method for one of the problematic users:
Export his mailbox to pst file - create a new mailbox - Import the pst file to the new mailbox, then test Outlook search function for the new user.
If an Answer is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.