We installed an exchange 2013 and created all the users from our AD to have an exchange account. But for some unexplained reason, the server crashed and we cannot recover the server.. due to HDD failure.. So we rebuild another server. Problem is all users mailbox resides to the dead server. And it will be a big work if we try to delete the existing exchange users and recreate them (500 users). If Ill delete the record of the old server on adsiedit. can we add again the AD users to the new exchange?

Hello

Havent got backup from 2013? or database file only?
you need recover server:

https://technet.microsoft.com/en-us/library/dd876880%28v=exchg.150%29.aspx

Recover the server with the exact same name. You are going to have do that anyway, because the adsiedit method of removing the server is not supported. Once you have recovered the server you can then either move the mailboxes to the new server and remove the old one correctly, or continue to use it.

For 500 users you aren't using a DAG? I think every implementation over 200 users I have done has had a DAG.

Simon.

This is just phase 1 of our project, this is supposed to be hybrid..

DAG is not part of the plan.

Problem is as we format the old server, mailbox are included.. no Backup..

Do I need to delete the adsiedit of the old server?

Formatting the server doesn't make any difference. All of the configuration information is stored in the domain.

Therefore you can completely recover the server back to the point it was at - minus the data. Don't try and shortcut things, particularly if you are going hybrid - it will cause you nothing but problems.

Simon.

Is there anyway on how can I recover the server config?

The old server is named tfsphmail5, and I just renamed it after formatting to tfsphmail6. I successfully did everything, from pre-requisites and installing exchange. But when I opened ECP, there are existing config and users. 

So I tried moving users from mail5 to mail6

the last option, for me, since I'm new to this scenario is to delete ADSIEDIT

The mailboxes are gone it sounds like. But if the AD accounts still point to the old server and you want to point them to the new server you can try this below. ( And they start with empty mailboxes)

See Step6 for an example:

https://technet.microsoft.com/en-us/library/Dd876926%28v=EXCHG.150%29.aspx?f=255&MSPPError=-2147217396

After the database is mounted, modify the user account settings with the Set-Mailbox cmdlet so that the account points to the mailbox on the new mailbox server. To move all of the users from the old database to the new database, use the following syntax.

Get-Mailbox -Database <SourceDatabase> |where {$_.ObjectClass -NotMatch '(SystemAttendantMailbox|ExOleDbSystemMailbox)'}| Set-Mailbox -Database <TargetDatabase

I'll be recreating this same scenario on a virtual environment by tomorrow. hope this will work. thanks a lot guys.. I'll give you a feedback tomorrow