Hi,
I’m afraid the issue is somewhere on your end – this would have been reported by now.
The default ajax handler can be accessed, but it seems to be blocking on POST requests. The message seems to be coming from WordPress, so there might be a programmatical block of the some requests.
If you use any plugins or custom code snippets that may do changes to user permissions, accessing content, user roles or anything similar – make sure to check those as well. In WordPress the ajax search requests are registered as actions to specific handlers, where WordPress checks the permissions. If the permissions of the logged out user had been altered in some way, that could explain the issue.