1. A method, comprising: storing a plurality of messages in a persistent message store, wherein the plurality of messages are copies of original messages transmitted from message producers to message consumers through an enterprise service bus in a distributed computing system, the plurality of messages being stored with keys that are determined from at least one of message headers, message contexts or message bodies; storing a pre-generated message search rule that comprises a set of search criteria for finding messages with specific attributes that have been transmitted through the enterprise service bus; receiving, by a processing device executing a rules engine, a command from a remote requestor to search the plurality of messages in the persistent message store for at least one message of the plurality of messages having the specific attributes, the command including a search rule identifier associated with the pre-generated message search rule; and processing, by the processing device, the pre-generated message search rule based on the search rule identifier to search for the at least one message using the keys associated with the plurality of messages.