unable to add new email user

I am trying to add an email ID which was hosted earlier with another services to zoho. however i am not sure why zoho would not allow it. i am frequently getting the error that the user is already in your org. i have deleted the email ID's with my earlier service provider. and yet i am not sure why i am unable to add here.