A mobile communication device for access procedure enhancement is provided. In the mobile communication device, a wireless module performs wireless transmissions and receptions to and from a service network. Also, a controller module transmits an access probe to the service network via the wireless module, and retransmits the access probe in response to not receiving an acknowledgement of the access probe from the service network via the wireless module in a waiting period of time. The waiting period of time is determined according to a coherence-time related offset. The controller module further repeats the retransmission of the access probe until the acknowledgement of the access probe is received from the service network via the wireless module