How do you migrate a server with thousands of clients?

Imagine you work for either hotmail, or blogger. You have hundreds of servers (probably more), each storing, and serving thousands of customers. How do you migrate that server to newer software? Without incurring downtime. How do you make sure that the software you are implementing does not break something that your customer uses? What if the customer is happy with the way things are, and they dont want to change anything. But you have to because of security issues or such. What does an admin do in that case? Mind you this is not one or two customers, this hundreds or thousands.