When do a search from the web, you actually author a document (though the Save Options are set to '0'); you need the access rights to create the document. This is why anonymous users can't search a database where you have set Default and Anonymous access rights to No Access. There are several workarounds:
1) Allow Default and/or Anonymous to have Author access, but change the Form Properties on each form so that users with specific Roles can create the normal forms in the database.
2) Create a Search Site database where the default access is Author. You can run searches from this database without compromising the security on other databases.
3) Give Default access the ability to create Public Access documents. Then, set your Search Form so it is available to Public Access Users.
4) Hand code the query URL as suggested by Torben Moelgaard:
What actually happens when you fill out the web-form, is that a url like this is built by the browser:
www.corp.com/db/view?searchview&query=apple+and+pie
<input type=text name=Input>
<input type=button onClick="location.href='http://www.corp.com/db.nsf/$defaultview?searchview&query=' + document.forms[0].Input.value">
<form onSubmit="return(false)"> ... </form>