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