This was ultimate work shared by my office colleagues to remove the Exchange server entries if server where not removed properly.
Removing AD Configuration
The list of Exchange servers on the domain is stored in the Active Directory configuration. Following steps below to remove the obsolete server:
1. Log on to the Domain Controller.
2. From the Start menu select Run… and enter adsiedit.msc to launch the ADSI Edit tool
3. In the tool, right-click ADSI Edit and select Connect To…
4. In the Connection Settings dialog under Select a well-known Naming Context select Configuration and click OK
5. Navigate to CN=Configuration [domain] → CN=Services → CN=Microsoft Exchange → CN=[organization] → CN=Administrative Groups → CN=Servers
6. Right-click and Delete the container for the offending Exchange server.
The Active Directory also stores information about the mailboxes that were located on the non-existent server. To remove these, perform the following steps in the ADSI Edit tool:
1. Navigate to CN=Configuration [domain] → CN=Services → CN=Microsoft Exchange → CN=[organization] → CN=Administrative Groups → CN=Databases
2. Identify the Mailbox Database containers that belonged to the lost server and Delete them.
Make sure that you are not deleting working mailboxes from the list, if you delete any by mistake you will have to delete & recreate the entire user using Active Directory Users & Computers. If there are multiple Exchange servers on the network, the Mailbox Database folders to delete can easily be identified by clicking on the folder and checking the Name field of the first entry, which should contain the name of the lost computer. Do not delete references to databases belonging to other Exchange servers!
Removing Security Settings
Now that the server is removed, some other settings need to be cleaned up as well. Perform the following additional steps on the domain controller:
1. Launch Server Manager
2. Navigate to Roles → Active Directory Domain Services → Active Directory Users and Computers [domain] → [domain] → Microsoft Exchange Security Groups
3. Remove the computer from the members list of Exchange Servers
4. Remove the computer from the members list of Exchange Trusted Subsystem.
If the computer was removed from the network altogether, you may also want to remove it from the Active Directory’s list of computers, as well as the DNS Server’s Forward Lookup Zones.
Please note that the above steps will work for Exchange 2007 / 2010 & 2013