Well I did allow for existing CC3 domain recycling in my earlier post :( It's a case of weighing up a variety of pros and cons for each approach and those are overwhelmingly site specific (to include local politics). I wouldn't want to do gradual at all, but as above an Exchange would give me pause for thought re. a new domain, as would any serious investment in account/group permissions in any network service or parts of the file system. Anyway since you're doing the recycle angle..
My approach was different: I kept the existing domain.