Unexpected permissions behavior

We have a space that is set for no permissions to anonymous users, and view permissions to "all".
Still, users can't access this space unless we remove the restriction to view from anonymous, regardless if they are logged on or not.