A wireless mobile telephone (400) is operated so as manage the performance of "off-frequency searches," that is, searches for base station pilot signals that differ in frequency from the pilot signals in the mobile station's active set. Whenever frequency searching is performed (such as responsive to emerging from a reduced-power sleep mode), the mobile station performs on-frequency pilot signal searching (902) upon a prescribed active set frequency. Only if a prescribed off-frequency searching condition (903-908) is satisfied, the mobile station additionally performs off-frequency pilot signal searching (912) upon one or more neighboring base stations' frequencies.