A method performed by a messaging host (110 1 -110 N) in a distributed messaging system, comprising: receiving, from a gateway, a request for any available message or set of related messages contained in any of a plurality of messaging entities (116 1 -116 N) hosted by the messaging host, wherein a set of related messages is comprised of messages having an identical message session identifier; identifying a subset of the plurality of messaging entities that contain at least one available message or set of related messages, wherein identifying comprises determining that the subset of the plurality of messaging entities is identified in a data structure, said data structure identifying each of the plurality of messaging entities that contains at least one available message or set of related messages and identifying the at least one available message or set of related messages for each identified messaging entity; assembling an ordered list of the messaging entities in the subset of the plurality of messaging entities; determining a particular messaging entity in the subset that is at the beginning of the ordered list and selecting a particular message or set of related messages contained by the particular messaging entity; removing the particular message or set of related messages from the data structure and locking the particular message or set of related messages contained by the particular messaging entity until expiration of a time period; removing the particular messaging entity from the ordered list and moving the particular messaging entity to an end of the ordered list in response to determining that the particular messaging entity still contains at least one available message or set of related messages after the request has been serviced; sending, to the gateway, a response that indicates that the particular message or set of related messages can be accessed by a client that caused the request to be issued, the response being cached by the gateway and then expired therefrom upon expiration of the time period; determining whether the particular message or set of related messages is still available after the request has been serviced; and adding the particular message or set of related messages back to the data structure in response to determining that the particular message or set of related messages is still available after the request has been serviced. receiving, from a gateway, a request for any available message or set of related messages contained in any of a plurality of messaging entities (116 1 -116 N) hosted by the messaging host, wherein a set of related messages is comprised of messages having an identical message session identifier; identifying a subset of the plurality of messaging entities that contain at least one available message or set of related messages, wherein identifying comprises determining that the subset of the plurality of messaging entities is identified in a data structure, said data structure identifying each of the plurality of messaging entities that contains at least one available message or set of related messages and identifying the at least one available message or set of related messages for each identified messaging entity; assembling an ordered list of the messaging entities in the subset of the plurality of messaging entities; determining a particular messaging entity in the subset that is at the beginning of the ordered list and selecting a particular message or set of related messages contained by the particular messaging entity; removing the particular message or set of related messages from the data structure and locking the particular message or set of related messages contained by the particular messaging entity until expiration of a time period; removing the particular messaging entity from the ordered list and moving the particular messaging entity to an end of the ordered list in response to determining that the particular messaging entity still contains at least one available message or set of related messages after the request has been serviced; sending, to the gateway, a response that indicates that the particular message or set of related messages can be accessed by a client that caused the request to be issued, the response being cached by the gateway and then expired therefrom upon expiration of the time period; determining whether the particular message or set of related messages is still available after the request has been serviced; and adding the particular message or set of related messages back to the data structure in response to determining that the particular message or set of related messages is still available after the request has been serviced.