Hey Christina,
I am about to remove a bunch of hard bounces from my database as well. From my understanding, if you delete a lead in Marketo, they will not sync back unless their information in SFDC is update. If it is updated, Marketo will recognize the change in data and sync the lead back.
For my company, we have set up sharing criteria between SFDC and Marketo. One of the criterias is that the lead/contact must have an email address that contains an @ symbol to sync to Marketo. What I am planning to do is export the list of hardbounces from Marketo and then use DataLoader to erase the email addresses out of our SFDC database. After I have completed this, I will remove them from Marketo and they will not sync to Marketo again unless a new email address is update.
Hope this makes sense and helps - and best of luck as you do your updating.
Taylor