Depends how disposable the individual servers are. I don't know specifics of the Twitter infra, but I would probably just issue a new cert and begin shooting and replacing the old servers. Hopefully the services are abstracted from the puppet cert and things like Redis and whatnot will safely reprovision and find their quorums.