This sounds like synchronous request-response calls with the GetAndWait API? I think multiple machines listening to the same queue will have exactly the problem you describe. Can you do a Get with the correlation id? I seem to recall something like that, but it involves scanning messages in queue and might be slow.
We use dynamic reply-to queues. MQ creates a temporary queue (from a template - low overhead) for every request. The response gets back to that queue and precisely the correct waiting
thread with no ambiguity. Can you try that configuration?