This also breaks the Always-Anonymous Categories plugin when the category has restrictive trust level settings.
It would be intuitive to copy the trust level to the anonymous user. On the other hand, this is a broader issue: categories could not just be trust-restricted but they can be restricted by any group membership, which would require syncing (and continuously re-syncing) all the users groups to the anonymous user. That could definitely be misused to figure out an anonymous user’s actual user.
Maybe it would work to be able to set default trust level and groups for the anonymous users?