Hmm, that's not the whole story. You can change the Display name of the organization quite easily within Admin - the underlying directory name does't change, but you hardly ever see that. If you have multiple sites, you need to connect to a server in each site to effect the change.
Alternatively, instead of reinstalling Exchange, you can use Move Server Wizard to move each server to a new org. Okay, it's probably as desruptive in the long run as reinstalling Exchange, but it has different advantages and at least it is another option available to you.