Чтобы понять, что происходит, вам нужно знать, как настроено время жизни сервисного объекта, к которому вы подключаетесь. Хорошей отправной точкой является статья MSDN о сеансах, экземплярах и параллелизме .
Например, с InstanceContextMode.PerCall будет создаваться новый объект службы для каждого вызова, поэтому свойства объекта службы не будут запоминаться между вызовами.
На другом конце шкалы InstanceContextMode.Single означает, что один экземпляр обрабатывает все клиентские запросы за время существования приложения. В этом случае свойства, установленные одним клиентом, будут видны всем клиентам, что обычно нежелательно.
В общем, я бы рекомендовал использовать объект службы без сохранения состояния. Но если вам нужен объект службы с состоянием (например, объект со свойствами), вы должны использовать InstanceContextMode.PerSession и (важно) использовать привязку, поддерживающую сеансы.
Хотя я согласен с @JTew в том, что вы вообще не должны представлять операции в качестве свойств, у вас будет та же проблема, если вы попытаетесь использовать объект, который хранит состояние между вызовами другим способом (например, частное поле). То есть следующее будет иметь точно такую же проблему:
[ServiceContract]
public interface IEcho
{
[OperationContract]
void SetMessage(string message);
[OperationContract]
string GetMessage();
... etc ...
}