A method and system for sending messages including multimedia content between mobile communication devices via relays. Synchronized local caches are maintained at the relays for storing and retrieving multimedia content originating with end-users, without the necessity of storing the multimedia content into the caches upon publication by a service provider. When a first mobile communication device wishes to send multimedia content to a second mobile communication device, the first mobile communication device initially transmits a digest of the multimedia content to a first relay, rather than the entire multimedia content, and the first relay searches a first local cache maintained by the first relay using the digest to determine whether the multimedia content is stored in the local cache. When the multimedia content is stored in the first local cache, the first relay sends to the second relay a reference to the multimedia content. By utilizing synchronized local caches and transmitting digests and references for multimedia content, redundant transfers of the entire multimedia content are eliminated.