I have been having this issue for quite some time now:
After I restore my iPhone to factory settings and signed in my iCloud account, the call logs would come back mysteriously, even ones dating back a few months that I have deliberately deleted.
This is really scary if you think about it.
There does not seem to be anyone else asking this particular question.
How may I solve this problem?