I have reset my iPhone, now many contacts are lost, though I synced them through iCloud. Are they still in an old backup? I reset my iPhone 4 because it was terribly slow after 3 years of continuous usage.

Now it's much faster again, but many of my contacts are lost, although I used to sync them using iCloud and I had them both on my phone and on my Mac. I tried to restore them using TimeMachine, but it seems there are no backups for contacts left from early enough.

Now I wonder whether my contacts still are on an old iPhone backup (which I should have in iTunes from before resetting my iPhone) and so I could get them back.

So my question is: What could have happened that I lost most of my contacts? I indeed deleted a lot of contacts a few days ago, but I for sure didn't delete many of those that are gone, and many that I deleted, are back again.
Not sure what happened but you should be able to restore your iPhone from within iTunes. Depending on when the backup was made that should have everything that was on your iPhone.

If you have no backups in iTunes that work you can check Time Machine for other backups:

/Library/Application Support/MobileSync/Backup/


Restore your more recent backup to your local HD and then Option-Click on the restore from backup button in iTunes and select the file you just recovered.

I am doing some of this from memory but that is the general idea.