1. Do you have security applied at the service level or the folder level (the folder where the service is published into on ArcGIS Server)?
2. Are you using Portal for ArcGIS, and if so, is Portal Federated with ArcGIS Server?
3. Which version of ArcGIS Server are you using?