Saving message order in WCF service using ConcurrencyMode.Multiple mode

There is a WCF service that processes incoming requests and for each incoming message produces a corresponding output message, which is sent to another WCF service. The order in which messages are received is important and cannot be broken. Thus, the service must issue the appropriate output messages in the same order in which they are received by the service. It is also important to process requests simultaneously in order to benefit from a multi-core processor.

What is the best approach to maintaining message order between inputs and outputs in this case?