A mobile communication device including a wireless module and a controller module is provided, and the mobile communication device is coupled to a cellular access station. The wireless module performs wireless transmissions and receptions to and from the cellular access station. The controller module determines whether a GAPM has been received from the cellular access station via the wireless module and whether the mobile communication device supports an EACH, and if so, performs Tx operations on the EACH using a random access procedure with a message duration, and otherwise, if not, performs the Tx operations on an ACH using the random access procedure. Particularly, the GAPM includes a maximum message duration and a minimum message duration over the EACH, and the message duration is not greater than the maximum message duration and not less than the minimum message duration over the EACH.