Just to be sure I am adding this doc: Delete Person from SFDC - Marketo Docs - Product Documentation .
As it written in the doc" If you set Delete in Marketo to true and delete the people from Marketo and the leads from Salesforce, they are gone forever. This can't be undone."
How much time passed since you restored the records and they still didn't show up?
I would just export from SFDC and import through Marketo. They will sync and merge (if you have 1:1). Your SFDC create date and MKTO create date will be different, but it should solve the issue.