A mobile communication device with a wireless module and a controller module is provided. The wireless module performs wireless transceiving to and from a first service network. The controller module transmits a location update request message to a first cellular station of the first service network via the wireless module, and receives a location update rejection message, which comprises a rejection cause indicating a network related failure, from the first cellular station via the wireless module. Also, the controller module transmits another location update request message to a second cellular station of the first service network via the wireless module in response to the location update rejection message. Particularly, the first cellular station and the second cellular station belong to a first location area and a second location area, respectively.