Removing a defunct Exchange Server from AD:
ADSI Edit to Configuration\Services\Microsoft Exchange\<org name>\Administrative Group\Exchange Administrative Group (FYDIBOHF23SPDLT)\Servers
+CN=[ServerName] Delete from this point including all child-items
If you have any exchange 2003 public folder references or routing groups, those will need to be deleted as well. They can be deleted using the management console if you prefer.