If you delete your leads in Marketo who are part of a program/campaign and it's synced to an SFDC campaign, I beleive they are still a member of the SFDC campaign.
I deleted some records from Marketo who were part of a program/campaign and was synced to an SFDC campaign. When their records were cleaned up in SFDC and made available to sync back to Marketo, I noticed that they were still in the SFDC campaigs.
It might be different if you removed them from a Marketo program first before deleting them from the Marketo database.