Before you can remove an Exchange server from your org, you need to get all the mailboxes off of it. I was working on a Exchange 2007 CCR migration and found that there was still a long dead Exchange 2000 server in the org. The admin had tried to delete it, but it reported that there was still a mailbox on the server. He had checked every AD account for it to no avail. If you want to find out what AD accounts still have resources on a specific server:

  1. Start ADUC on the Exchange server, assuming it Windows 2003.
  2. Right click on your domain at the top and choose “Find”.
  3. Click on the “Advanced” tab.
  4. Under “Field”, select User, then “Exchange Home Server”.
  5. Change the “Condition” from “Starts With” to “Ends With”.
  6. In the “Value” field, type in the old Exchange server name and then click add to set the value.
  7. Click find to start a search.

You can then open that user account and clear out the Exchange settings that are holding you back.