New lead unsubscribed without ever receiving an email

Could be a few explanations, but in my experience this is usually when one person has some type of alias set up -- meaning they're receiving mail that you are sending to the email address corresponding to their record in your database, but their primary address (and often in this case, the one they think you are sending to) is different.

I pull new leads every day to gauge response by our sales reps. I feel like if this were an alias, or email forwarding issue, that it would happen either sporadically, or I would see it more often in my daily reports. In this particular case, I saw several for one day after never encountering this issue prior.

maybe someone is abusing your unsubscribe form? How far apart were the submissions? 

we faced the same issue lately, also contacts reverting to us to be unsubscribed while they weren't even in our database. After checks it seems it was due to a redirect to another email address, probably people who left the company and emails were redirected to another email address, also some forward. Not much that can  be done about this unfortunately. Luckily it doesn't happen often. 

Anecdotal marketing observations, but I've seen emails sent to me with a small line in the footer, "This email was sent to {{email address}}.  To unsubscribe, click here."  Putting the intended recipient email address near the unsubscribe link can help tip off people who are receiving emails forwarded from other mailboxes.

If it starts to looks like people are unsubscribing with a different email address than the one you have in your database, you might want to consider populating the email address you have in the unsubscribe form. This way, the prospect stops getting contacted and you don't get additional lead records that don't want to hear from you.