Deletion in SFDC I do not believe always deletes in Marketo, UNLESS you ran the deletion from Marketo.
What tends to happen is that Marketo retains things like the SFDC Record Type ID and SFDC ID values. Because SFDC does not have that info any more, Marketo views it as an error on sync.
So you should:
- erase the SFDC ID and Record Type IDs in Marketo
- push sync the records
- verify they are recreated in SFDC
assuming you want the leads back in SFDC.