First, I'm sure you've already tried these suggestions. However, here are some ideas.
Could you run a report of users and the email address or apply a view in the users list, then export it into excel. Then you can do a search on the email column to see if you can find something similar.
Or could this person be under a different username than you have? For instance, we've run into situations where, let's say, we are notified that the new user is Robert, but someone puts him in as Rob or Bob?
When searching for a user, make sure you double check by not using the whole name in the search. Use only the last or first name. You might catch something that way.