SharePoint 2013 Custom List / Document Library – Search Box

I have encountered a strange issue with the SP2013 search box.

I have a series of custom lists and document libraries on the same site. The majority of them are open access to all of my colleagues (via a ‘contribute’ permission level group and the use of the ‘everyone’ profile within this group). On all of these lists/libraries the search box works perfectly for all colleagues (i.e. at both ‘contribute’ level and super-user level)

However, on a handful of lists/libraries that include specific colleague names in the ‘contribute’ group (because the content is more confidential), the search box only works for the super-users. Colleagues in the ‘contribute’ group see the ‘there is nothing to display’ message when searching – even though there clearly is data to display!

I hope my explanation makes sense. Thanks in advance for any help/advice.