I actually don't restrict anything, including search, to guests. All content is viewable/downloadable and everything is searchable. My thought process is such that if I restrict something to force guests to register, 99% of them are likely to register, get what they're wanting, and never come back again. That last 1% would've probably ended up registering anyways. I'm a bit of a neat freak, so I don't like the idea of having thousands of registered members who will never post on the site, and will probably never even come back again. I used to regularly delete all users that hadn't visited the site in over a year and had 0 posts. I stopped doing that for various reasons, but I still don't like them being there.
What add-on is that you're using to see what folks are searching for?