You need to make it replicate to all clients. One way to do this is to create a custom event and then have it replicate the destroy.
Connection would be setup with your event replacing the current destroy node and then having your custom event fire off the destroy node.