In WCF, if a contract operation has a void return and is not one way, there is no message ID attached to the reply. I didn't check this up with all bindings but it does happen with basicHttp and wsHttp bindings atleast. (http://www.w3.org/TR/2006/REC-ws-addr-core-20060509/ defines this).
The problem doesn't arise if the communication is WCF-WCF. You might encounter this only with WCF- non-WCF SOAP (Websphere) communication.
A very simple solution is to have a custom message inspector which checks if the response message has an ID. If not, it inserts one.
The code sample is attached.