Ok, finalmente percebi depois de horas pesquisando e testando. Eu tive que usar o ADSI Edit para remover o armazenamento de pasta pública do domínio, então eu era capaz de desinstalar com sucesso o antigo servidor de troca. Pode não ser bonito, mas funcionou:
Em ADSIEdit
, vá para Configuration
, Configuration
, Services
, Microsoft Exchange
, <YOUR ORGANIZATION>
, Administrative Groups
, Exchange Administrative Group
, Servers
, <SERVER NAME>
, Information Store
, %código%. Em seguida, no painel à direita, destaque <STORAGE GROUP NAME>
e exclua.