I am sure you just have to make sure that all your permissions are configured correctly.
check the Group permissions for anonymous user group.
check the Category permissions for anonymous user group (sounds like you've already set this, although I think maybe you need view_category as well, somebody else confirm?)
check that the object (e.g. Wiki page) that is categorized has global permissions, not special permissions.