A cellular communications system may include at least one base station selectively denying attempts to establish wireless communications links therewith, and wirelessly transmitting denial messages for denied attempts. The system may further include at least one mobile cellular communications device including a wireless transceiver and a controller cooperating therewith for attempting to establish a wireless communications link with the at least one base station having a quality of service (QoS) level associated therewith. If a denial message is received, the controller continues to attempt to establish the wireless communications link at a first attempt rate. Yet, if the wireless communications link cannot be established with the desired QoS level, and if no denial message is received, then the controller continues to attempt to establish the wireless communications link at a second attempt rate different than the first attempt rate.