@sam It seems to work now, but looks like there is one corner case left (which screwed us up a bit today 
)
It is possible to delete all permissions on the Security tab when creating the subcategory, and then the subcategory (e.g. of the staff category) will be created successfully and visible to everyone.