But after all the discussion about Dustin's AA or Andrew's Zappos redesigns, I don't know how the fact still didn't catch up, that creating the first mockup isn't that big of a deal, and the real work can't be done not taking into account any requirements or business goals :)
And unfortunately from a user's standpoint, a redesign is one of the worst things that could happen to a site. Because however cramped and difficult a site might be, there are people who use them daily, and changing the structure completely overnight would abandon the most loyal users. That's why it's easy for startups to come up with nice sites in 2010, they haven't had a website since 1995 so they don't have the baggage of previous users.
So as much as a redesign, I'd appreciate not a complete overhaul but sort of a compromise, that would improve usability without forcing old users to relearn everything. A good alternative is having the old and new site co-exist for a while, to get feedback on the new site as well, but not all companies unfortunately have resources for that.