Wenn sie sich nicht in iCloud/Kontakte befinden, sind die Kontakte leider verloren.
Gibt es vielleicht noch ein Backup in iTunes auf dem Computer? Dort sind die Kontaktdaten Teil des Backups.
Man müßte aber dann das iPhone aus diesem Backup herstellen, die Kontakte mit iCloud synchronisieren und danach das iPhone wieder löschen und vom letzten iCloud Backup wiederherstellen.
Dann wären die Daten und Einstellungen aktuell, und ein erneutes Einschalten von "Kontakte" in iCloud würde letztendlich diese Informationen wieder aktualisieren.