Also, while the DNS is switching there would be some major database inconsistencies between the two server stacks. How do you deal with that?
Could you clarify what you mean by database inconsistencies between stacks?
What property do you work on? How is it more efficient to buy or reallocate entirely new servers than update your old ones?
How many times per year do you even update your application? The cost of getting the servers ready and installing packages would be prohibitive if you had to roll out, say, an urgent security fix.
When doing a major release seldo is spot on. Especially given the small amount of time it takes for hardware to get out of date it's often cheaper to provision new hardware prior to the major release and then deploy straight onto that. Mostly the old boxes would then get cycled back in to production, something less strenuous like staging, or retired.
For the really huge properties, the cross-colo upgrade pattern you (sh1mmer) describe is the way to go.
Also, cross-colo is not a factor of being big, it's a factor of having a BCP (business continuity plan). Every team at Yahoo is urged to have BCP for practically everything. I used to do cross-colo upgrades for a relatively small project once we had more than two frontend servers.
I image cheap way to fake multiple colos now is to use visualization, amazon style. Heck you could do exactly what Seldo was suggesting every time on EC2.
Also, the new Buzz site used all new hardware (and was a new product) and Games rolled out on new hardware when it was upgraded from HF2K to PHP. The old servers were reimaged and folded in with their PHP siblings once it was clear that the build was holding up properly.
Basically, hardware is much cheaper than downtime, and very big web companies have lots more money. So we don't swap out old servers gradually: instead we buy and set up an entirely new set of servers, deploy to them several weeks in advance of the planned launch, and run QA against these production-level boxes. Then, when we are ready to "launch", all we're really doing is a relatively low-risk DNS change: all the potentially tricky deployment issues having been ironed out beforehand.
After a couple of weeks/months of operation on the new hardware, if there have been no major problems, the old boxes are decommissioned -- either re-imaged and put back into service to expand capacity, or more often taken out of service entirely (I've no idea what we do with old boxes when we stop using them, funnily enough).