Certainly the companies who had the potential to lose that much money shouldn't have been relying on the hosting company to do all the work! Our co-lo center moved to the next building and out "90 minutes max." downtime was over 3 hours during prime time for us. I would assume comparable underestimation for a move that far.
First, if I'd received a letter like that I probably would have started looking for a new hosting company ASAP. If I had to have my servers moved anyway, I'd decide where they would go.
Second, if I decided to stick with the company, I would probably be involved with the move myself. unless I had too much hardware to replicate, I'd probably buy some servers to put in the new data center, mirror the sites, then switch DNS over to the new servers well before the move. So downtime would (should) be negligible.
Then again, you're right, if you're making that much money, you should have a disaster recovery plan in effect long before a move, including a completely cloned setup at a different data center. I'd have DNS switched over to that data center well beofre the move and would switch it back until everything was well tested at the new data center.