I have deleted some users, and now I want to recover onen of them. But I have a mesage that the user name and his email already exist.
Go into the Users section in the WP back end and type in the username that exists. You should find a record if it is still there.
Deleting users completely deletes them - there is no "trash" normally, so the user should no longer exist in the database unless you have a plugin which keeps them.