Careful, it's not just about branding. You have to live the brand idea as well, it has to perspire in your products, down to the tiniest detail. Anyone can hire a new brand team, pour millions in TV ads and new copies, but that won't change squat until the products themselves follow the very same idea.

At a company scale such as Microsoft's, true rebranding will take significant time and resources, or they will have to take hard hits first before they realize they have to change something.

As you mentioned in your example, you can rebrand yourself from one day to another and pretend it's the new "you", but you can't move that fast when you have 100 000 employees who have to pull that act at the same time.