One illustrative method for use by a host server in pushing messages to a mobile communication device involves the steps of causing a message to be sent to a relay network for delivery to the mobile communication device through one of a plurality of wireless communication networks which are communicatively coupled to the relay network; receiving, from the relay network, a result message when the mobile communication device is unavailable to receive the message through the wireless communication network, the result message comprising a message identifier which uniquely corresponds to the message; maintaining storage of the message in memory accessible by the host server after the result message is received; receiving, from the relay network, a status message which indicates that the mobile communication device is available to receive the message when the mobile communication device is available to receive the message through the wireless communication device; and causing the message to be sent again to the relay network for delivery to the mobile communication device in response to receiving the status message. During the unavailability of the mobile device, the relay network refrains from maintaining storage of the message in memory of the relay network.