Почему бы не использовать CorrelationId?
var message = new Message(new Messageval(), new BinaryMessageFormatter());
message.CorrelationId = messageId;
queue.Send(message);
И затем получить сообщение как это:
var resp = (Messageval) queue.ReceiveByCorrelationId(messageId,
TimeSpan.FromSeconds(30))
.Body;
CorrelationId должен состоять ровно из 20 байтов, иначе при назначении будет выдано исключение.