Access to the CGI is restricted to authenticated HTTP users. In general, this is as it should be. However, searching is handled by the CGI too. Browsing doesn't require authentication; searching shouldn't either.
(Also, while I'm at it, RecentChanges links to recently edited pages via the CGI, and those links should work for unauthenticated users too. Any other operations to be whitelisted?)
Fixed with a locally applied patch (will be in the next release) from Joey. --schmonz
Search results all start with our web template crud. Would be nice if the previews showed page content instead.