Anonymous users can't search

Did you make sure to rebuild your search index. and run a cron job. It might just be that its not indexing the items for anon users, hence why it works for auth users and not for non auth users.

Dear Drupalists.

the problem described by briantes is not singular:

1) if I grant anonymous users the permission (admin/people/permissions) to
a) "Use search" AND
b) to "Use advanced search"
then anonymous users can then and only then use advanced search if I also
check the box "Search all content" for anonymous users under the heading
Search Configuration.

2) if I grant anonymous users the permission to search all but one of the content
types (checked boxes in "Search configuration") AND both boxes "Use search"
and "Use advanced search" (heading: Search) are checked but the box
"Search all content" is unchecked then anonymous users may well use the basic
search but the advanced search (I tried it with negation combined with OR ("any"-
inputbox) doesn't work for the anonymous users anymore, the NO-RESULT message
shows up.

3) leaving all else the same and just rechecking the box "Search all content" for
anonymous users they can use advanced search again (the to-be-expected
search results show up).

I ran two cron jobs after each change of permissions and also cleared the caches
(...performance...) but all to no avail.
I'm using Drupal 7.7 and I get the feeling that there really is a bug.

I think the "override" stated below the "Search all content"-text is faulty, it overrides
also positive settings set below if the uppermost ("Search all content") is unchecked.

Can anybody please help?

Thank you very much,
Georg Huber.