Today one of my users encountered this error while trying to add a new SMTP address to an existing account.
The proxy address “smtp:email@example.com” is already being used by “contoso.com/Microsoft Exchange System Objects/BI176-Folder”. Please choose another proxy address.
This is an Exchange 2007 mailbox, to troubleshoot, I used ADSIEdit.msc tool to find the Exchange object causing the error, and under “class” it was marked “Public Folder”, on the properties dialog, I could see under proxyAddresses attribute, the email address mentioned in the error.
Using PFDAVAdmin I was able to connect to the public folders in the organization and find one of the subfolders that was using the SMTP address in the error. I requested user to choose another SMTP address just as the error prompt suggested and that solved it. If the Exchange object is already orphaned and no longer in use in your organization you can delete it or rename the proxy-addresses attribute.