Why can't anonymous users search for any users, even after the administrators have configured permissions to search user profiles?

This happens because the Search Groups for anonymous users were not configured in Search Permissions. Make sure to explicitly grant access to specific groups.

Anonymous Search Permissions