Are you saying there is a replyTo header on the server with a generated queue name, but that queue was never created? The reason I ask is that the replyTo queue name is generated as a result of declaring the queue.
Is it possible the client is timing out before the response is received? In that case, the reply queue will be deleted. The default reply timeout is 5 seconds, but it can be increased using the replyTimeout property on the RabbitTemplate.
Also, the recent spring-amqp 1.1.0 release supports a fixed reply queue, which should work out of the box when the producer and consumer are both Spring Integration applications.
<rabbit:template id="withReplyQ" connection-factory="connectionFactory" reply-queue="reply.queue">
Gary P. Russell
Spring Integration Team
SpringSource, a division of VMware