Hi Darwin,
I would open a case with support to be sure.
However, you can try and track this down by looking at a lead's activity log and seeing if there are any Sent Email activities. If not, the lead probably didn't get the email. If there are some, he likely did. That said, someone should look at your individual lead with you to make sure- and to investigate/fix whatever caused the issue to happen.