Not only does it depend on the business case as indicated by this answer, it also depends on your level of risk tolerance in the code's design. Tight coupling between the client and the service can make the code more difficult to change as the application grows and increases in complexity. Instead, a clean separation of responsibilities and loose coupling generally increases maintainability and overall project agility.
In this case, that would probably mean the service wouldn't know about the existence of the client and it's implementation, so that would rule out the service directly manipulating the client list. If this service is implemented as a class library, I would recommend a publisher/subscriber approach, where the service exposes a C# event of a type that includes pertinent deletion information, and the client handles that event and updates it's list accordingly.
If this is a web (one-way) service, I would expect the a deletion service call to be separate of a GetAll service call. The client would manually manage it's list using a combination of those calls.