A service consumer that utilizes a cloud-based access service provided by a service provider has associated therewith a network that is not capable of being controlled by the service provider. An enterprise connector is supported in this uncontrolled network, preferably as an appliance-based solution. According to this disclosure, the enterprise configures an appliance and then deploys it in the uncontrolled network. To this end, an appliance is required to proceed through a multi-stage approval protocol before it is accepted as a “connector” and is thus enabled for secure communication with the service provider. The multiple stages include a “first contact” (back to the service) stage, an undergoing approval stage, a re-generating identity material stage, and a final approved and configured stage. Unless the appliance passes through these stages, the appliance is not permitted to interact with the service as a connector. As an additional aspect, the service provides various protections for addressing scenarios wherein entities masquerade as approved appliances.