I used GetRelatedEntities method to pull all related entities into collection and then use this collection to disassociate all related entities:
DisassociateRequest disassociateRequest = new DisassociateRequest();
disassociateRequest.Relationship = new Relationship("new_appointment_contact");
disassociateRequest.Target = new Microsoft.Xrm.Sdk.EntityReference("appointment", id);
EntityReferenceCollection referenceCollection2 = new EntityReferenceCollection();
Entity existingAppointment = _service.Retrieve("appointment", id, new ColumnSet(true));
foreach (Entity item in existingAppointment.GetRelatedEntities(orgContext, "new_appointment_contact"))
{
Guid contactId = new Guid(item["contactid"].ToString());
Microsoft.Xrm.Sdk.EntityReference entityReference2 = new Microsoft.Xrm.Sdk.EntityReference("contact", contactId);
referenceCollection2.Add(entityReference2);
}
disassociateRequest.RelatedEntities = referenceCollection2;
_service.Execute(disassociateRequest);