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.