Hi Rachel,
The behavior you described would happen if the Contact was deleted in SFDC. Contacts that are deleted in SFDC are not deleted from Marketo so all the information is there. Then when the record was synced to SFDC (or was added to an SFDC Campaign), it would be pushed back into SFDC as a new lead. Marketo can't create Contacts, only Leads.
You need to understand who/what deleted the Contact in SFDC to begin with and address that issue. It was not Marketo that deleted the Contact.
Hope this helps.