Yes, once the leads are synched to Marketo they become records in Marketo's database. If you delete them in Salesforce they should delete in Marketo, but changing sharing rules just removes Marketo's visibility into those records, and it would seem Marketos' version of the record will just live on happily after that.
(If this assumption is correct, changes to records in SFDC should no longer synch for these records as Marketo can't see them -- it would be interesting to test to make sure that is the case.)
Anyhow, to delete those records (assuming they are all leads/contacts with no email address as you mentioned):
1) Create a smart list with filter
Email Address Is Blank
+ any other criteria as appropriate
2) Go to the leads tab and click "Select all"
3) Click the "Delete Lead" button to delete the leads making sure to NOT delete from SFDC (in theory Marketo shouldn't be able to delete the SFDC record anyhow, but to be safe...)
IMPORTANT: Again I strongly urge you to test, test, test, before doing a batch delete of 75K leads. But that is the process I would use.
Good luck!