Restricted nodes don't show up in search results
The default Drupal search respects the Drupal permission system, so if the user performing a search doesn't have permission to see a node, it won't appear in search results at all. To get around this, you'll need something that circumvents the permission system, either by altering the search function, or replacing it entirely.

You could take a look at the Custom Search module. It modifies Drupal's search, and gives you control over the default search options. However, I can't recall if it includes an option to show content you wouldn't otherwise have permission to see.

The other way you could do it is to create a custom view, add a filter for the field you want to search on, then under advanced, select "query options", and tick the "disable query rewriting" option. This will prevent the permissions from being applied to the view, so will allow users to see nodes they don't have access to. However, I'm not aware of any way of making a view search multiple fields from a single exposed filter, making it less than ideal for an alternative search box.