Is it possible to execute queries in random order?
From your application layer, stamp each query with a timestamp and batch ID. Instead of executing the queries, store them in a temporary table with the format

sql_test | timestamp | batchID


When you know all queries from a batch have been received, kick off a stored proc that retrieves all queries from the batch, orders by timestamp asc and executes them

You'll probably want to add more logic about establishing dependencies between batches and how to deal with failed error,etc