Lead Should Be Unsubscribed

Maybe instead of searching for his email address in your lead database search for his first and last name, he might have subscribed with a different email address that is forwarding emails onto another address.

A long shot but I can't see any other reson he would be receiving your emails if he doesn't even exist as a lead in your database.

He does not exist according to First Name, Last Name, or Email Address...very odd

Was the person able to forward you the email that they claim to have recieved from you?

You should be able to tell if it was sent via Marketo or not, for example are the links branded for tracking.

Often we find this to be the case of an email being forwarded, as Cathal has suggested. The person might not even know that his previous co-worker's emails are being forwarded to him, for example. 

If they can forward you the email, you might be able to work through a process of elimination to determine the correct email address that should be unsubscribed. 

I've seen several instances of the case that Dory suggested where a previous coworker's email is sent the their inbox.  You can generally track these down with a smart list of Company Name and Was Sent Email, to identify records from the same company.  Alternate company names, subsidiaries, and email domains can make the process of finding the record a bit trickier, however.