Methods and systems for implementing message batching in a distributed strict queue are disclosed. A plurality of messages are distributed to a plurality of queue servers based on strict order parameters for the messages. Messages that share a value for the strict order parameter are distributed to the same queue server. The messages are enqueued at the queue servers. Messages that share a value for the strict order parameter are enqueued in a strict order based on the time of receipt at the queue server. A batch comprising individual messages is sent to a queue client. The messages that share a value for the strict order parameter are batched in the strict order.