Leads deleted in SFDC

You're right, there isn't a direct option for that. However, you might consider creating a lead status or otherwise setting a field on the lead that indicates it has been deleted. That would make it easy to filter out of your lists.

You could also take them out, export full records for offline storage.

Another, perhaps better option all together, would be to create an archive partition that is visible to a select audience and move those leads to that partition so you have access to the data but it it isn't in the active partition. You could then have logic that moves it between partitions if they are reinstituted and then you have the ongoing information.

Thank you both for the suggestions. I am intrigued by the idea of the partition - how would I do that?

You'd need to have the Enterprise Editon of Marketo and then ask to enable workspaces and partitions. In general, if you're not already using partitions, I wouldn't enable the feature just to deal with archived leads.

When leads are moved out of the active partition into the archive partition are they excluded from reports, analyzers and RCE?  If so, we wouldn't archive them until a couple of years after they went dormant (e.g. no longer at company).

Unfortunately we do not have the Entrerprise Edition of Marketo so partitions are not an option. Considering the last comment, it does not look like deleting them is a good idea either.