This is true. And it's actually a battery saving technique. The phone will attempt to transmit and make a connection with the weakest possible transmission power possible. If that fails, then it kicks up the power and tries again.
You have it backwards. Phones don't transmit when they are looking for a tower, they LISTEN. The tower has MUCH more transmit power than the phone does, so when you are out of range, it is likely you can hear the tower, but it can't hear you.
And when the phone does try to make initial contact with the tower, it does so at the highest possible power level. The tower then tells it to reduce the transmit power, if it is too high.
The tower is smart about receiving initial contacts too. It reserves some time slots for such attempts, in effect saying "if you're trying to get in touch with me, do so NOW". It has to do this because of the propagation delay - it doesn't know how far away you are, and doesn't want you to transmit all over a time-slot that is reserved for someone else.