Unfortunately there is a known bug where global search does not pick up records a user is entitled to see through team based permissions. The two work arounds for this are:
If a record does not appear in global search, instruct users to search in the module directly using these steps:
Go to the module
Click the blue Create button next to Filter
From the first dropdown select what you would like to search on
From the second dropdown select Exactly Matches
In the text box that appears type the relevant text
Edit the permissions on the user's role in the list column from "Owner and Selected Teams" to "All". This will mean the records are now visible in global search. It will also make all records visible in the list view to the customer, but they will only be able to click into ones they have permissions for
If you do not use team based permissions or you cannot search for any records, you may need to perform the steps found 'here'