In the specs, it is just said :
The MS is checking cells in descending order of received signal strength. If a suitable cell is found, the MS camps on it and performs any registration necessary.
The number of channels to be searched are 15 for GSM 450, 15 for GSM 480, 25 for GSM 750, 30 for GSM 850 Band, 30 for GSM 900 and 40 for DCS 1800 and PCS 1900.
After that, the MS stops looking.
It is also said that a mobile *might* keep the last BCCH in memory, during the previous swith-off, so when it is started again, it will look for that BCCH again.
So, yes, the MS will scan the whole band, but just in order to find the strongest channels (this is fast). Then it will decode the strongest channels, and see whether they belong to its PLMN or not.