Mailbox creation issue

Sounds like the attributes on the account were deleted during mailbox deletion.
First things first however, check if it already has a mailbox enabled by opening the Exchange CMDlet and running

Run Get-Mailbox -Identity "DOMAIN\Username"

If the user has a mailbox, you will need to remove it first.
If that is not the case, compare attributes with a working user.
Compare to the attributes of a working user account. (Might be easier to delete user, replicate the change, and after 15 min or so (Just in case) re-create the account.

Another option could be something wrong with  security settings on the AD account.

1] Go to active directory users and computers.
2] Under view, enable "Advanced Features"
3] Double click the affected user
4] Go to the security tab, and click on advanced
5] Make sure that the "Include Inheritable Permissions" are selected

Let me know how you go with these 3 suggestions.

I have "Removed Exchange Attributes" at Active directory just today.

"Include Inheritable Permissions" is selected.

Are you implying that the suggestions provided did not work for you?
What is the error received when creating user in powershell?
Enable-Mailbox john@contoso.com -Database "MyServer\Mailbox Database"

And does the user still show as mail enabled when running Run Get-Mailbox -Identity "DOMAIN\Username"?

I have renamed user logon name to different.
Copy this user with his settings and create logon name (that we were lokkign for).

Create mailbox at EMC (used existing user).

The issue has been resolved.

Thanks.