A call processing system, which may include multiple distributed call center sites, utilizes a local back-off approach to endpoint registration. The call processing system comprises a plurality of endpoints and at least a first server, wherein the endpoints register with the first server in order to send and receive calls in the call processing system. Responsive to an end-to-end connectivity failure or other designated event, a registration process is initiated in the call processing system for a given one of the endpoints. The issuance of at least one message of the sequence for the given endpoint is controlled so as to provide a local random back-off or other local back-off of the controlled message at that endpoint. For example, a second server implemented as an aggregation server may be operative to control the issuance of messages by the endpoints so as to provide a local random back-off for each of the plurality of endpoints by staggering the delivery of failure notifications to the endpoints.