Guests on my 3.7.4 board cannot do any searches, including using "Today's Posts" - when they try to search they are met with the registration rules agreement screen.
I've already looked in the usergroup and the Unregistered /Not Logged In group already has the following options checked: