Service providers collect user’s personal information relevant to their businesses. Personal information stored by different service providers is expected to be combined to make new services. However, specific user records risk being identified from the combined personal information, and the user’s sensitive information may be revealed. Also, personal information collected by a service provider must not be disclosed to other service providers because of security issues. Thus, several researchers have been investigating distributed anonymization protocols, which combine the personal information stored by the providers and sanitize it to ensure an anonymity policy with minimum disclosure. However, when providers have different sets of the users, there is a problem that the existence of users in either service provider may be revealed. This paper introduces a new notion, δ-max-site-presence, which indicates the probability of the existence of users being revealed in a distributed environment and a new distributed anonymization protocol for hiding the existence of users. Our evaluation results show that the proposed protocol can anonymize users in accordance with the policy of hiding their existence and user anonymity without too much information loss.