Several related methods and apparatus for re-establishing communication for a wireless communication device after a communication loss between the wireless device and a wireless communication network are disclosed. In one illustrative example, the wireless network broadcasts identifiers of wireless devices associated with communication losses in the wireless network over a control channel. After regaining signal coverage, a wireless device monitors the control channel to decode and compare each broadcasted identifier with an identifier of the wireless device. Based on a match between a broadcasted identifier and the identifier of the wireless device, the wireless device transmits a control message which informs the wireless network of the presence of the wireless device. Otherwise, the wireless device normally refrains from transmitting the control message to the wireless network. Advantageously, communication with the wireless network is re-established (if at all necessary) without overburdening the wireless link with unnecessary traffic.