I would have a process which immediately processes the (hopefully short) fallback queue, writes the required info to a non-distributed database and then posts the message to the main fallback queue for further processing.
You can then add a fallback query to this central database in the case that the code isn't found.
Hopefully at any given time you only have a small number of these anomalous first messages, so although this adds a central point of failure to your system, it is fast enough not to affect overall performance.
If the query is being made by the same client as the initial request, ie i make a booking and then immediately load it on the next page, then I would remove the second request altogether. If you have the information locally just use it.
Regarding your duplicate key problem, rather than attempt to search your distributed db and various queues for duplicates, which would be an inherent bottleneck, use a unique generation strategy such as giving the client reserved lists of ids, composite ids which include the client id, or one of the "short guid" algorithms