Hi @Matthew Ries,
Check if the user has the necessary permissions to perform a search in SharePoint Online. Make sure the problematic users have the same permission as normal users, or she has at least Read permission on the content that she wants to search.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
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.