Emmanuel - When Marketo is synced to a SalesForce instance and the lead from Marketo is deleted and also set to remove from SFDC (see below screenshot), you can use the "DeleteLeadFromSales" activity type and get a list of deleted leads.
Here is the test I ran:
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<ns2:paramsGetLeadChanges xmlns:ns2="http://www.marketo.com/mktows/">
<startPosition>
<activityCreatedAt>2013-10-25T15:14:13.034-07:00</activityCreatedAt>
</startPosition>
<activityFilter>
<includeTypes>
<activityType>DeleteLead</activityType>
<activityType>DeleteLeadFromSales</activityType>
</includeTypes>
</activityFilter>
<batchSize>100</batchSize>
</ns2:paramsGetLeadChanges>
Response:
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<ns2:successGetLeadChanges xmlns:ns2="http://www.marketo.com/mktows/">
<result>
<returnCount>25</returnCount>
<remainingCount>0</remainingCount>
<newStartPosition>
<latestCreatedAt xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:nil="true"/>
<oldestCreatedAt>2013-10-25T15:14:13.034-07:00</oldestCreatedAt>
<activityCreatedAt>2013-10-25T15:14:13.034-07:00</activityCreatedAt>
<offset>ID:12281825</offset>
</newStartPosition>
<leadChangeRecordList>
<leadChangeRecord>
<id>12281801</id>
<activityDateTime>2013-10-25T17:37:57-05:00</activityDateTime>
<activityType>Delete Lead from SFDC</activityType>
<mktgAssetName>sd 1</mktgAssetName>
<activityAttributes>
<attribute>
<attrName>Lead ID</attrName>
<attrType xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:nil="true"/>
<attrValue>1321071</attrValue>
</attribute>
</activityAttributes>
<mktPersonId>1321071</mktPersonId>
</leadChangeRecord>
<leadChangeRecord>
.......
</leadChangeRecordList>
</result>
</ns2:successGetLeadChanges>