We normally remove from the cluster and swap out, like you do. We are currently running six VMs as our server farm (which was scaled up from four physical machines, to account for VM overhead). We rotate three out at a time, as well. The rule of thumb we follow is that at least half of the nodes need to be available at any given time to keep the site up, otherwise, we pull the entire site.
Also, we are very seriously considering using a warm "image" server that is out of the cluster that can be deployed to, tested, and then imaged for deployment. The assumption is that the image will be completely tested and we can minimize downtime for deployment and not have to go through a full series of smoke tests for each node.