Ciao,
Se il tuo iPhone usava Outlook come predefinito per i contatti, molto probabilmente i tuoi contatti sono salvati nel tuo account Microsoft e non in iCloud.
Per prima cosa, prova a controllare i contatti di Outlook online. Basta accedere a Outlook punto com con lo stesso account sul tuo iPhone, poi andare nella sezione Persone e vedere se compaiono i contatti mancanti.
Sul tuo iPhone, apri Impostazioni, poi Contatti, poi Account, e assicurati che il tuo account Outlook sia presente e che l'interruttore Contatti sia attivato. Se non vedi l'account, aggiungilo di nuovo andando su Impostazioni, Mail, Account Appropriati, Aggiungi account, poi scegli Outlook e attiva la sincronizzazione Contatti.
Se i contatti sono stati cancellati, Outlook ti permette di ripristinarli entro 30 giorni usando l'opzione Ripristina contatti sul sito di Outlook.
Solo una nota, i contatti non vanno su OneDrive a meno che tu non li abbia esportati tu, quindi non saranno lì se non lo hai fatto. Una volta trovati i contatti in Outlook, tieni semplicemente l'account Outlook attivato per i contatti sul tuo iPhone e dovrebbe sincronizzarli di nuovo.
Spero che questo ti sia d'aiuto!