Introduction
The error message "User already exists" occurs when the domain administrator is trying to create a new mailbox.
Useful Info
Creating an email account has as a result the creation of a user too.
Warning!
Deleting an email account does not mean that the user will be deleted too
Step 1 - Fix the error
Search the 
list for one with the “already exist” mail, delete that user and restart the mail account creation.
Conclusion
This error message exists only because the administrator forgot to delete the user that was linked to the mailbox which was deleted in the past.