If the client isn't sure that the delete has gone through, just do it again once reconnected (to server 2 in the scenario described). Whatever response you get for the delete should determine what you need to do.
FYI - this is why Curator has “guaranteed" deletes. So many recipes depend on the delete succeeding. -JZ
