I have the same problem. As an admin, I'll give permission to my teacher to see a serach box in the participants list... Let's wait for a pretty answer
Do you have multiple pages of users to search through? I notice that Moodle doesn't provide a search box if all users appear on just one page.
I don't know if the question was ever answer but you need to change the role permission in order to access the search bar feature for teachers/instructors(any postion that is not an admin)
If you are using Moodle 1.9 go to Users > Permissions > Define Role > click on the edit hand for the position > under the system categories grant "view participants."
This should solve the problem.
Sorry it is 3 years late. lol