Privacy-Preserving Record Linkage (PPRL) supports the integration of sensitive information from multiple datasets,in particular the privacy-preserving matching of records referring to the same entity. PPRL has gained much attentionin many application areas, with the most prominent ones in the healthcare domain. PPRL techniques tackle thisproblem by conducting linkage on masked (encoded) values. Employing PPRL on records from multiple (more thantwo) parties/sources (multi-party PPRL, MP-PPRL) is an increasingly important but challenging problem that so farhas not been sufficiently solved. Existing MP-PPRL approaches are limited tofinding only those entities that arepresent in all parties thereby missing entities that match only in a subset of parties. Furthermore, previous MP-PPRL approaches face substantial scalability limitations due to the need of a large number of comparisons between maskedrecords. We thus propose and evaluate new MP-PPRL approaches that find matches in any subset of parties and stillscale to many parties. Our approaches maintain all matches within clusters, where these clusters are incrementallyextended or refined by considering records from one party after the other. An empirical evaluation using multiple realdatasets ranging from 3 to 26 parties each containing up to 5 million records validates that our protocols are efficient,and significantly outperform existing MP-PPRL approaches in terms of linkage quality and scalability.