Hi Matt,
Usually, it's because there is a smart campaign somewhere that detects lead deletion from SFDC and delete them from Marketo. Finding it in a non documented instance might be painful since, by definition, all leads that went through this smart campaign are gone... And there is no activity log to look into.
When setting this type of SC, it's better to start it with a wait step, BTW. SFDC keep leads in the Recycle bin for a max of 15 days, so waiting 14 days and checking the lead is still deleted is OK. It will make sure that, if the lead is undeleted in that 14 day period, it ill also remain in Marketo. Waiting more than 16 days is not good, because then the lead is gone from SFDC and the sync is in error. I am not sure in this case that the "lead is deleted" filter still works correctly. I have never been in a situation where I could test it.
-Greg