Have you verified if the lead is there in Salesforce or has been deleted? It seems the record exists in Salesforce but Marketo Salesforce Sync user doesn't have appropriate permissions to read/update this lead.
Refer to the url for verifying if permission issue is the case Step 2 of 3: Create a Salesforce User for Marketo (Enterprise/Unlimited) - Marketo Docs - Product Docs
Are there other leads facing same issue?
The lead was deleted from what I can tell. I now want to recreate the lead in SFDC but cannot by syncing from Marketo because it is looking for the old SFDC ID. Does that make sense?
I have heard of this happening to people however I could not remember how to resolve.
If I remember right there isn't much of a resolution to it. You may try creating a new lead and then merging the old one into the new one.
In my experience, the best way to troubleshoot sync errors is to keep the marketo sync user's SFDC login handy, and then try logging into SFDC with it and see if you can view the record, make modifications to it, etc.