I just saw this article about Google's data-driven design philosophy. It seems Google will not make design choices unless they are backed by quantitative findings that the change is a measurable improvement; users vote with their clicks.
Adhering too rigidly to a design philosophy guided by “Web analytics,” Ms. Dunn [of the Stanford Institute of Design] said, “makes it very difficult to take bold leaps.”
And as much as it may sound jarring, the customer is not always right.
“Customers sometimes do not know what they want,” said John Seely Brown, the co-chairman of the Deloitte Center for Edge Innovation, a research and consulting organization based in Silicon Valley. “It can be dangerous to just listen to what users say they need.”
This quote reminded me of an interesting story about eBay: eBay's website originally had a yellow background, until one day the company decided it would rather have a white one. Overnight, they implemented the white background and the next morning woke up to screaming protests from upset users. These were people who had spent hours - days! - tweaking their storefronts to the point that they considered their mini-sites to be their own rather than property of eBay. For the parent company to suddenly swoop in and adjust their backgrounds was inconceivable. The outrage was so intense that eBay restored their former yellow background right away.
But the company wasn't going to give up so easy, and over the next few months engineers gradually reduced the website's "yellowness." Each night, eBay's background shifted imperceptably toward white. Most importantly, no one complained, even when the website finally became a pure white after a few months of gentle tweaking.
The moral of the story - people like what they know. We don't really mind change all that much; we just overwhelmingly fear what we don't know. Gradual introduction of new features (unless people "know" they want them) can successfully introduce the necessary comfort level that leads to their acceptance.
Exhibit B: Facebook's experience with major UI changes. However, Facebook has responded by acquiescing to users and allowing them to vote on prospective changes - it remains to be seen whether this approach will be successful or truly necessary.
By the way, the answer to the title question is: very rarely.
Update: I was unable to remember where I read the eBay story, and the only documentation I've found is this blog post on gradual redesigns. Maybe they also rewrote history while I wasn't looking...