1. A method for use by a relay network in pushing messages to a mobile communication device, the method comprising the acts of: receiving, at the relay network, a message from a host server for delivery to the mobile communication device through one of a plurality of wireless communication networks which are communicatively coupled to the relay network; causing a result message to be sent to the host server based on identifying that 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; refraining from maintaining storage and management of the message in memory of the relay network after the result message is sent to the host server; causing a status message which indicates that the mobile communication device is available to be sent to the host server based on identifying that the mobile communication device is available to receive the message through the wireless communication device; and receiving again, at the relay network, the message corresponding to the message identifier from the host server for delivery to the mobile communication device in response to the status message being sent to the host server.