One illustrative method of reducing undeliverable server-initiated IP traffic within a wireless network (21) includes the steps of identifying that a data connection (e.g. a Packet Data Protocol or PDP Context) for communicating server-initiated IP messages from a host server (22 or 26) to a mobile station (10) has been lost or terminated; causing a notification message having a destination address corresponding to the host server (22 or 26) to be produced based on identifying that the data connection has been lost or terminated; and causing the notification message to be sent to the host server (22 or 26). The notification message may cause the host server (22 or 26) to at least temporarily refrain from communicating and/or to queue server-initiated IP messages (10) intended for the mobile station (10). The notification message may be formatted and communicated based on an existing protocol, such as Internet Control Message Protocol (ICMP), or any other suitable protocol.