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 workarounds 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 don't use team based permissions or can't search for any records, follow the steps here.