If you do not delete the record in both systems, SFDC can reinsert it into Marketo under various circumstances. The other problem is if the lead comes back into Marketo with the same email, it will try to sync to SFDC. When that happens, as Ed said, it may push a duplicate.
Not sure why you are deleting records in this situation, but if you do, I recommend deleting in both systems, and to export the list before you do so.