Since, as OP says, non-members occasionally could find the channel, it was probably a public channel. The people who complained were probably "multi-channel guests". They'd see masked-out channel names except where they are explicitly allowed.
Ah, no, they wouldn't have been guests. The organisation was large enough that it had multiple “workspaces” corresponding to different divisions. Channels always belong to a workspace, but some are shared between workspaces. You can only see the channels belonging to or shared with your workspace.
Since, as OP says, non-members occasionally could find the channel, it was probably a public channel. The people who complained were probably "multi-channel guests". They'd see masked-out channel names except where they are explicitly allowed.