Hey Keith,
When a lead is deleted from SFDC but not Marketo, two things occur. First a "Delete Lead from SFDC" action is logged and second, the field "SFDC is Deleted" is set to true. If you later attempt to resync the lead to SFDC, a new lead record will be created there and the "SFDC is Deleted" flag will be set back to false. There shouldn't be any issues when trying to resync the lead back to Salesforce.