Exchange error c10312e7 when adding a new email address

I was asked to create a new user with an email address on our Exchange server. Sounds simple enough, and I expected it to take all of 2 minutes. However, after I added the user, the email address was different than what I wanted and had a number appended to it (e.g email@email.com was getting set up as email3@email.com). When I manually tried changing the SMTP address value, I received an error c10312e7 "This email address already exists in this organization". I had never set up the user before, and I know I had never used the email address before, yet a search on email addresses didn't help. I turned to Google and found the solution here. 

1. Open the Active Directory Users and Computers snap-in

2. Right-click the domain and choose Find, or click the domain and go to Action->Find...

3. In the Find: box (which defaults to Users, Computers, and Groups) change that option to be Custom Search

4. To the right of that, in the In: box, change that to be Entire Directory

5. Click on the Advanced tab so you can directly input an LDAP query

6. For your LDAP query, use proxyaddresses=smtp:emailToFind@yourDomain.com

7. Click on Find Now. The results will display at the bottom, and you should find the Object causing you grief

Doing this solved my problem right away. It turns out that prior to my time at the company, someone had created a public folder on the Exchange server, and that folder had the email I was trying to use attached to it. The folder was never used, so I just deleted it and fixed the email address for the user I was creating. Seems like a pretty simple fix to an annoying problem.

I also found KB 280765, which may be an alternative for you if the above doesn't solve your issue.