A mobile communication device including Subscriber Identification Module (SIM) cards, and various methods for searching for a Public Land Mobile Network (PLMN) for each SIM card, are provided. In one method, the device separately starts Home PLMN (HPLMN) timers according to corresponding HPLMN timer values stored respectively in the SIM cards, performs a PLMN search for one of the SIM cards at an expiry of a corresponding one of the HPLMN timers, and updates a PLMN list with one or more PLMNs found during the PLMN search. The device then determines, for all of the SIM cards, whether the PLMN list contains any PLMN with a higher priority than a currently registered PLMN. Also, the device performs, for any SIM card of the SIM cards in which there is any PLMN with the higher priority than the currently registered PLMN, a location registration in the PLMN with the higher priority.