Declarative Workflow Services 4.0: Error - InstanceKeyNotFoundException

Problem Description

When working with declarative workflow services, you may get following error:

System.ServiceModel.Core: Throwing exception: System.ServiceModel.Persistence.InstanceKeyNotFoundException: The requested operation could not complete because instance key '3019110b-9313-ab7a-db1e-25e00cae4f5e' could not be found.
   at System.ServiceModel.Persistence.PersistenceProviderDirectory.LoadOrCreate(InstanceKey key, Guid suggestedIdOrId, Boolean canCreateInstance, ICollection`1 associatedKeys, Boolean throwOnThrottleExceeded, TimeSpan timeout)
   at System.ServiceModel.Persistence.PersistenceProviderDirectory.LoadOrCreateAsyncResult.OnLoadOrCreate()
System.ServiceModel.Core: Throwing exception: System.ServiceModel.Persistence.InstanceKeyNotFoundException: The requested operation could not complete because instance key '3019110b-9313-ab7a-db1e-25e00cae4f5e' could not be found.

Workaround

This exception is mostly thrown by receiving of messages, for example in ReceiveMessageAction which uses content based correlation. The error is handled internally by workflow service model, and it does not indicate any error in your workflow which expect to receive the message.
In opposite, the problem is caused by the sender of the message. Sender sends a valid message, but your receiver expects to reeive the message which can be correlated with one or running workflow instances.
For example you send two messages to service with Order=1 and Order=2 within two workflow instance. They both purchase orders separately. After a while, service may send notification about ordering status. If the service sends Order=1 and Order=2 (which are bound to correlation token) all will work fine. However, if the service sends valid message,but with Order=3 (which is not known by your receiver activity), the exception shown above will be created.