Вы поступили совершенно неправильно: не надо было чистить AD (штатного способа сделать это вообще нет) - а надо было устанавливать Exchange на сервер с тем же именем (причем вводить его в домен аккуратно: сначала переименовать,
перезагрузить, а потом уже вводить в домен - чтобы не потерять существующую учетную запись сервера) с ключом в setup.exe /mode:recoverserver (естественно - ту же версию с тем же SP и с теми же обновлениями)
Потому что основная часть конфигурации Exchange хранит в AD, и она отлично бы оттуда подцепилась. Только надо чтобы те папки, где раньше были базы, были и на новом сервере (они тоже в конфигурации прописаны). Ну и если использовались сторонние
сертификаты - надо было бы их установить.
А сейчас никакой гарнтии, что вы восстановите работу Exchange, нет - совершенно непонятно, что вы там вычистили, что нет. Если есть резервная копия AD - восстанавливайте её в полномочном режиме. Или, если в AD включена Корзина
- можно попробовать вытащить удаленное через ADSIEdit из Корзины. И ставьте после этого сервер Exchange в режиме восстановления, как положено.
Если же вы старую конфигурацию Exchange таки угробили с концами, то, чтобы старые пользователи были видны в интерфейсе создания п/я, очистите у них атрибуты, связанные с Exchange. Как это сделать - читайте здесь:
https://social.technet.microsoft.com/wiki/contents/articles/14347.remove-exchange-attributes-using-power-shell-exchange-2010.aspx
Слава России!
