When attempting to create a new user with an email that already exists, you will receive a message indicating that the email is not available. Either an active user already exists with that email or a user had previously been created and then deleted using that email.
If when you use the filter on the User Detail page to search for the email, it does not pop up, click on the "Show inactive" next to "Add user" and search again.
Users are not actually deleted, they are de-activated, so if the user was deleted you will be able to click on that user in the "Show inactive" list, and then click on the "Restore" button to re-activate the user.
