It's not true that IE must be reinstalled to remove branding. Branding is specified in a key in the registry.
You can remove the branding by editing the registry ('Start' -> 'Run', type 'regedit' in the window).
Can't remember the exact registry location but it's something like 'H_Key -> Local_machine -> Software -> Microsoft -> Internet_Explorer'.
The key that forces IE to use the branded icon is called 'Branding'. Removing this key stops the branding. IE uses its own logo by default if this key is not present.
Sorry I can't be more specific. Can't remember exactly because it's been a couple of years since I've had to do it.
A search of M$ knowledge base or possibly even Google et al should find the information to remove the branding.