I just recently deleted a large number of unsubscribed names from SFDC for the same reason - to cut down our data stora. I first created a static list in Marketo and added all names to it in case we ever needed to reference them, and then deleted in SFDC.
This may not be appropriate to your use case, but one thing that I have to constantly think about when creating email lists is what records I want to include - those that are in SFDC only, or those in both Marketo and SFDC. I often use the filter SFDC Type = Contact or Lead to make sure that I'm not accidentally including leads that I deleted from SFDC, even if they still fit my filter criteria.